Sökning: onr:"swepub:oai:DiVA.org:ltu-12613" >
Online routing in c...
Online routing in convex subdivisions
-
- Bose, Prosenjit (författare)
- School of Computer Science, Carleton University, Ottawa, Ontario, Canada
-
- Brodnik, Andrej (författare)
- Luleå tekniska universitet,Datavetenskap,IMFM, University of Ljubljana, Ljubljana, Slovenia
-
- Carlsson, Svante (författare)
- University of Karlskona/Ronneby, Karlskona, Sweden
-
visa fler...
-
- Demaine, Erik .D. (författare)
- Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA, United States
-
- Fleischer, Rudolf (författare)
- Department of Computer Science, Hong Kong University of Science and Technology, Kowloon, Hong Kong
-
- López-Ortiz, Alejandro (författare)
- Department of Computer Science, University of Waterloo, Canada
-
- Morin, Pat (författare)
- School of Computer Science, Carleton University, Ottawa, Ontario, Canada
-
- Munro, J. Ian (författare)
- Department of Computer Science, University of Waterloo, Canada
-
visa färre...
-
(creator_code:org_t)
- 2002
- 2002
- Engelska.
-
Ingår i: International journal of computational geometry and applications. - 0218-1959. ; 12:4, s. 283-295
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- online algorithms
- routing
- oblivious algorithms
- computational geometry
- Dependable Communication and Computation Systems
- Kommunikations- och beräkningssystem
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas