onr:"swepub:oai:DiVA.org:ltu-26846"
Search: onr:"swepub:oai:DiVA.org:ltu-26846" > Online routing in c...
- 1 of 1
- Previous record
- Next record
- To hitlist
Online routing in convex subdivisions
-
- Bose, Prosenjit (author)
- School of Computer Science, Carleton University, Ottawa, Canada
-
- Brodnik, Andrej (author)
- Luleå tekniska universitet,IMFM, University of Ljubljana, Ljubljana, Slovenia
-
- Carlsson, Svante (author)
- University of Karlskrona/Ronneby, Karlskrona, Sweden
- show more...
- show less...
- (creator_code:org_t)
- 2002-01-29
- 2000
- English.
- In: Algorithms and Computation. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 3540412557 ; , s. 47-59
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
- Algorithms and Computation (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Bose, Prosenjit
- Brodnik, Andrej
- Carlsson, Svante
- Demaine, Erik D.
- Fleischer, Rudol ...
- López-Ortiz, Ale ...
- show more...
- Morin, Pat
- Munro, J. Ian
- show less...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Algorithms and C ...
- By the university
- Luleå University of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
