Back to Search
Start Over
Efficient Vertex-Label Distance Oracles for Planar Graphs.
- Source :
-
Theory of Computing Systems . Feb2018, Vol. 62 Issue 2, p419-440. 22p. - Publication Year :
- 2018
-
Abstract
- We consider distance queries in vertex-labeled planar graphs. For any fixed 0 < ϵ ≤ 1/2 we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex u and a label λ return a (1 + ϵ)-approximation of the distance from u to its closest vertex with label λ. For a directed planar graph with n vertices, such that the ratio of the largest to smallest arc length is bounded by N, the preprocessing time is O(ϵ-2 n lg3 n lg(n N)), the data structure size is O(ϵ-1 n lg(n N)), and the query time is O(lg lg n lg lg(n N) + ϵ-1). We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 62
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 128169823
- Full Text :
- https://doi.org/10.1007/s00224-017-9827-0