期刊
SIAM JOURNAL ON COMPUTING
卷 33, 期 4, 页码 937-951出版社
SIAM PUBLICATIONS
DOI: 10.1137/S0097539700369387
关键词
routing; online algorithms; Delaunay triangulations; shortest path; spanning path
We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include ( 1) two deterministic memoryless routing algorithms, one that works for all Delaunay triangulations and the other that works for all regular triangulations; ( 2) a randomized memoryless algorithm that works for all triangulations; ( 3) an O(1) memory algorithm that works for all convex subdivisions; ( 4) an O( 1) memory algorithm that approximates the shortest path in Delaunay triangulations; and ( 5) theoretical and experimental results on the competitiveness of these algorithms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据