Sökning: onr:"swepub:oai:DiVA.org:ltu-26846" >
Online routing in c...
-
Bose, ProsenjitSchool of Computer Science, Carleton University, Ottawa, Canada
(författare)
Online routing in convex subdivisions
- Artikel/kapitelEngelska2000
Förlag, utgivningsår, omfång ...
-
2002-01-29
-
Berlin :Encyclopedia of Global Archaeology/Springer Verlag,2000
-
electronicrdacarrier
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:ltu-26846
-
https://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-26846URI
-
https://doi.org/10.1007/3-540-40996-3_5DOI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:kon swepub-publicationtype
Anmärkningar
-
Godkänd; 2000; 20080313 (ysko)
-
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 och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Brodnik, AndrejLuleå tekniska universitet,IMFM, University of Ljubljana, Ljubljana, Slovenia(Swepub:ltu)brodnik
(författare)
-
Carlsson, SvanteUniversity of Karlskrona/Ronneby, Karlskrona, Sweden
(författare)
-
Demaine, Erik D.Department of Computer Science, University of Waterloo, Waterloo, Canada
(författare)
-
Fleischer, RudolfDepartment of Computer Science, University of Waterloo, Waterloo, Canada
(författare)
-
López-Ortiz, AlejandroFaculty of Computer Science, University of New Brunswick, Fredericton, Canada
(författare)
-
Morin, PatSchool of Computer Science, Carleton University, Ottawa, Canada
(författare)
-
Munro, J. IanDepartment of Computer Science, University of Waterloo, Waterloo, Canada
(författare)
-
Luleå tekniska universitetSchool of Computer Science, Carleton University, Ottawa, Canada
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:Algorithms and ComputationBerlin : Encyclopedia of Global Archaeology/Springer Verlag, s. 47-593540412557
Internetlänk
Hitta via bibliotek
Till lärosätets databas