| 1. |
- Bose, Prosenjit, et al.
(author)
-
Online routing in convex subdivisions
- 2000
-
In: Algorithms and Computation. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 3540412557 ; , s. 47-59
-
Conference paper (peer-reviewed)abstract
- 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.
|
|
| 2. |
- Bose, Prosenjit, et al.
(author)
-
Online routing in convex subdivisions
- 2002
-
In: International journal of computational geometry and applications. - 0218-1959. ; 12:4, s. 283-295
-
Journal article (peer-reviewed)abstract
- 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.
|
|
