Exact distance oracles for planar graphs
From MaRDI portal
Publication:5743390
zbMATH Open1422.68053arXiv1011.5549MaRDI QIDQ5743390FDOQ5743390
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1011.5549
Recommendations
- Better tradeoffs for exact distance oracles in planar graphs
- More compact oracles for approximate distances in undirected planar graphs
- Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
- Almost optimal distance oracles for planar graphs
- Approximate distance oracles for planar graphs with improved query time-space tradeoff
Information storage and retrieval of data (68P20) Data structures (68P05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
Cites Work
- A note on two problems in connexion with graphs
- Graph minors. X: Obstructions to tree-decomposition
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Call routing and the ratcatcher
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Approximation algorithms for NP-complete problems on planar graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Graph minors. II. Algorithmic aspects of tree-width
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- Distance Oracles for Sparse Graphs
- Distance Oracles beyond the Thorup--Zwick Bound
- S-functions for graphs
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- VC-Dimension and Shortest Path Algorithms
- Preprocessing Speed-Up Techniques Is Hard
- Title not available (Why is that?)
- Compact oracles for reachability and approximate distances in planar digraphs
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Diameter and treewidth in minor-closed graph families
- Faster shortest-path algorithms for planar graphs
- Experimental and Efficient Algorithms
- Computing the dilation of edge-augmented graphs in metric spaces
- Finding small simple cycle separators for 2-connected planar graphs
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Shortest paths in directed planar graphs with negative lengths
- Diameter and treewidth in minor-closed graph families, revisited
- Fast Routing in Road Networks with Transit Nodes
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Multiple-source shortest paths in planar graphs
- Compact Navigation and Distance Oracles for Graphs with Small Treewidth
- Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
- Title not available (Why is that?)
- Algorithms – ESA 2005
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Many distances in planar graphs
- Improved algorithms for dynamic shortest paths
- Title not available (Why is that?)
- Oracles for bounded-length shortest paths in planar graphs
- An external memory data structure for shortest path queries
- Algorithms and Computation
- Shortest path queries in planar graphs
- Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
- Improved Distance Queries in Planar Graphs
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
- Title not available (Why is that?)
- The Shortcut Problem – Complexity and Approximation
Cited In (18)
- Title not available (Why is that?)
- Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
- Title not available (Why is that?)
- A substring-substring LCS data structure
- Connectivity Oracles for Planar Graphs
- Exact Distance Oracles for Planar Graphs with Failing Vertices
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Reconstruction and verification of chordal graphs with a distance oracle
- Title not available (Why is that?)
- Short and Simple Cycle Separators in Planar Graphs
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
- Distributed planar reachability in nearly optimal time
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Fast and Compact Oracles for Approximate Distances in Planar Graphs
- Almost optimal distance oracles for planar graphs
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
- Title not available (Why is that?)
Uses Software
This page was built for publication: Exact distance oracles for planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743390)
