Efficient vertex-label distance oracles for planar graphs
From MaRDI portal
Publication:1743124
DOI10.1007/s00224-017-9827-0zbMath1390.68507arXiv1504.04690WikidataQ60143009 ScholiaQ60143009MaRDI QIDQ1743124
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
Related Items
Efficient dynamic approximate distance oracles for vertex-labeled planar graphs, The nearest colored node in a tree, Succinct data structures for nearest colored node in a tree, Efficient vertex-label distance oracles for planar graphs
Cites Work
- Unnamed Item
- 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 2 ) 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
- 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
