2015 | OriginalPaper | Buchkapitel
Tipp
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Erschienen in:
Approximation and Online Algorithms
We consider distance queries in vertex labeled planar graphs. For any fixed \(0 < \epsilon \le 1/2\) we show how to preprocess an undirected planar graph with vertex labels and edge lengths to answer queries of the following form. Given a vertex u and a label \(\lambda \) return a \((1+\epsilon )\)-approximation of the distance between u and its closest vertex with label \(\lambda \). The query time of our data structure is \(O(\lg \lg {n} + \epsilon ^{-1})\), where n is the number of vertices. The space and preprocessing time of our data structure are nearly linear. We give a similar data structure for directed planar graphs with slightly worse performance. The best prior result for the undirected case has similar space and preprocessing bounds, but exponentially slower query time. No nontrivial results were previously considered for the directed case.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Anzeige
1.
Abraham, I., Chechik, S., Krauthgamer, R., Wieder, U.: Approximate nearest neighbor search in metrics of planar graphs. APPROX/RANDOM
2015, 20–42 (2015)
2.
Chechik, S.: Improved distance oracles and spanners for vertex-labeled graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 325–336. Springer, Heidelberg (2012)
CrossRef
3.
Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci.
55(1), 3–23 (1997)
MATHMathSciNetCrossRef
4.
Hermelin, D., Levy, A., Weimann, O., Yuster, R.: Distance oracles for vertex-labeled graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 490–501. Springer, Heidelberg (2011)
CrossRef
5.
Kawarabayashi, K., Klein, P.N., Sommer, C.: Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 135–146. Springer, Heidelberg (2011)
CrossRef
6.
Kawarabayashi, K., Sommer, C., Thorup, M.: More compact oracles for approximate distances in undirected planar graphs. In: SODA 2013, pp. 550–563 (2013)
7.
Klein, P.N.: Preprocessing an undirected planar network to enable fast approximate distance queries. In: SODA 2002, pp. 820–827 (2002)
8.
Li, M., Ma, C.C.C., Ning, L.: (1 +
\(\epsilon \))-distance oracles for vertex-labeled planar graphs. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 42–51. Springer, Heidelberg (2013)
CrossRef
9.
Lipton, R., Tarjan, R.: A separator theorem for planar graphs. SIAM J. Appl. Math.
36, 177–189 (1979)
MATHMathSciNetCrossRef
10.
Łącki, J., Ocwieja, J., Pilipczuk, M., Sankowski, P., Zych, A.: The power of dynamic distance oracles: efficient dynamic algorithms for the steiner tree. In: STOC 2015, pp. 11–20 (2015)
11.
Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM
51(6), 993–1024 (2004)
MATHMathSciNetCrossRef
- Titel
- Efficient Vertex-Label Distance Oracles for Planar Graphs
- DOI
- https://doi.org/10.1007/978-3-319-28684-6_9
- Autoren:
-
Shay Mozes
Eyal E. Skop
- Sequenznummer
- 9