Name
Abstract | ||
|---|---|---|
We present I/O-efficient algorithms to construct planar Steiner spanners for point sets and sets of polygonal obstacles in the plane, and for constructingthe "dumbbell" spanner of [6] for point sets in higher dimensions. As important ingredients to our algorithms, we present I/O-efficient algorithms to color the vertices of a graph of bounded degree, answer binary search queries on topology buffer trees, and preprocess a rooted tree for answeringprioritized ancestor queries. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-44634-6_27 | WADS |
Keywords | Field | DocType |
bounded degree,polygonal obstacle,o-efficient shortest path queries,planar steiner spanner,rooted tree,geometric spanners,important ingredient,o-efficient algorithm,point set,answeringprioritized ancestor query,higher dimension,binary search query,binary search,shortest path | Discrete mathematics,Combinatorics,Tree (graph theory),Shortest path problem,Vertex (geometry),Computer science,Steiner tree problem,Spanning tree,Binary search algorithm,Spanner,Binary search tree | Conference |
Volume | ISSN | ISBN |
2125 | 0302-9743 | 3-540-42423-7 |
Citations | PageRank | References |
2 | 0.36 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anil Maheshwari | 1 | 869 | 104.47 |
| Michiel H. M. Smid | 2 | 550 | 93.58 |
| Norbert Zeh | 3 | 55 | 6.97 |