Online routing in convex subdivisions
2000 (English)In: Algorithms and Computation: 11th International Conference, ISAAC 2000 Taipei, Taiwan, December 18-20, 2000 Proceedings / [ed] D.T. Lee; Shang-Hua Teng, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2000, 47-59 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2000. 47-59 p.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1969
Research subject Dependable Communication and Computation Systems
IdentifiersURN: urn:nbn:se:ltu:diva-26846DOI: 10.1007/3-540-40996-3_5Local ID: 01abe9d0-f100-11dc-ba03-000ea68e967bISBN: 3-540-41255-7OAI: oai:DiVA.org:ltu-26846DiVA: diva2:1000026
International Symposium on Algorithms and Computation : 18/12/2000 - 20/12/2000
Godkänd; 2000; 20080313 (ysko)2016-09-302016-09-30Bibliographically approved