Efficient vertex-label distance oracles for planar graphs

DOI10.1007/s00224-017-9827-0zbMath1390.68507arXiv1504.04690OpenAlexW3021279856WikidataQ60143009 ScholiaQ60143009MaRDI QIDQ1743124

Eyal E. Skop, Shay Mozes

Publication date: 12 April 2018

Published in: Theory of Computing Systems, Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.04690

zbMATH Keywords

planar graphsapproximate distance oraclesportalsshortest-path separators

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (5)

The nearest colored node in a tree ⋮ Unnamed Item ⋮ Succinct data structures for nearest colored node in a tree ⋮ Efficient vertex-label distance oracles for planar graphs ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Planar separators and parallel polygon triangulation.
• Efficient vertex-label distance oracles for planar graphs
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Deterministic Dictionaries
• Improved Distance Oracles and Spanners for Vertex-Labeled Graphs
• Approximate Distance Oracles with Improved Bounds
• The Power of Dynamic Distance Oracles
• Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
• Distance Oracles for Vertex-Labeled Graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Constructing Efficient Dictionaries in Close to Sorting Time
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• A Separator Theorem for Planar Graphs
• (1 + ε)-Distance Oracles for Vertex-Labeled Planar Graphs
• Approximate Nearest Neighbor Search in Metrics of Planar Graphs
• Distance Oracles beyond the Thorup--Zwick Bound
• Compact oracles for reachability and approximate distances in planar digraphs
• Structured recursive separator decompositions for planar graphs in linear time
• More Compact Oracles for Approximate Distances in Undirected Planar Graphs
• Faster shortest-path algorithms for planar graphs

This page was built for publication: Efficient vertex-label distance oracles for planar graphs