Efficient dynamic approximate distance oracles for vertex-labeled planar graphs
Publication:5915659
DOI10.1007/978-3-319-89441-6_20zbMath1436.68247arXiv1707.02414OpenAlexW2752743218WikidataQ60143006 ScholiaQ60143006MaRDI QIDQ5915659
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
planar graphs\(\varepsilon\)-coverapproximate distance oraclesportalsvertex labels\(\epsilon\)-cover
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Data structures (68P05) Approximation algorithms (68W25)
Uses Software
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
This page was built for publication: Efficient dynamic approximate distance oracles for vertex-labeled planar graphs