Efficient dynamic approximate distance oracles for vertex-labeled planar graphs

DOI10.1007/978-3-319-89441-6_20zbMath1436.68247arXiv1707.02414WikidataQ60143006 ScholiaQ60143006MaRDI QIDQ5915659

Itay Laish, Shay Mozes

Publication date: 22 June 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/1707.02414

zbMATH Keywords

planar graphs; \(\varepsilon\)-cover; approximate distance oracles; portals; vertex labels; \(\epsilon\)-cover

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68P05: Data structures

68W25: Approximation algorithms

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient vertex-label distance oracles for planar graphs
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Improved Distance Oracles and Spanners for Vertex-Labeled Graphs
• Amortized Bounds for Dynamic Orthogonal Range Reporting
• The Power of Dynamic Distance Oracles
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
• Distance Oracles for Vertex-Labeled Graphs
• Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A Separator Theorem for Planar Graphs
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
• (1 + ε)-Distance Oracles for Vertex-Labeled Planar Graphs
• Approximate distance oracles
• Shortest-path queries in static networks
• Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
• Compact oracles for reachability and approximate distances in planar digraphs
• More Compact Oracles for Approximate Distances in Undirected Planar Graphs
• Faster shortest-path algorithms for planar graphs