Exact distance oracles for planar graphs
From MaRDI portal
Publication:5743390
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
Cites work
- scientific article; zbMATH DE number 5734722 (Why is no real title available?)
- scientific article; zbMATH DE number 219245 (Why is no real title available?)
- scientific article; zbMATH DE number 2119743 (Why is no real title available?)
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- A note on two problems in connexion with graphs
- Algorithms and Computation
- Algorithms – ESA 2005
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- An external memory data structure for shortest path queries
- Approximation algorithms for NP-complete problems on planar graphs
- Call routing and the ratcatcher
- Compact navigation and distance oracles for graphs with small treewidth
- Compact oracles for reachability and approximate distances in planar digraphs
- Computing the dilation of edge-augmented graphs in metric spaces
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
- Diameter and treewidth in minor-closed graph families
- Diameter and treewidth in minor-closed graph families, revisited
- Distance Oracles for Sparse Graphs
- Distance oracles beyond the Thorup-Zwick bound
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Experimental and Efficient Algorithms
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fast Routing in Road Networks with Transit Nodes
- Faster shortest-path algorithms for planar graphs
- Finding small simple cycle separators for 2-connected planar graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. X: Obstructions to tree-decomposition
- Highway dimension, shortest paths, and provably efficient algorithms
- Improved algorithms for dynamic shortest paths
- Improved distance queries in planar graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Many distances in planar graphs
- Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
- Multiple-source shortest paths in planar graphs
- Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
- Oracles for bounded-length shortest paths in planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Preprocessing speed-up techniques is hard
- S-functions for graphs
- Shortest path queries in planar graphs
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Subgraph Isomorphism in Planar Graphs and Related Problems
- The Shortcut Problem – Complexity and Approximation
- VC-dimension and shortest path algorithms
Cited in
(21)- Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
- scientific article; zbMATH DE number 7559259 (Why is no real title available?)
- Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
- scientific article; zbMATH DE number 7561410 (Why is no real title available?)
- Multiple-source shortest paths in planar graphs
- A substring-substring LCS data structure
- Connectivity Oracles for Planar Graphs
- An efficient oracle for counting shortest paths in planar graphs
- Better tradeoffs for exact distance oracles in planar graphs
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Near-optimal distance emulator for planar graphs
- Reconstruction and verification of chordal graphs with a distance oracle
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Distributed planar reachability in nearly optimal time
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- Improved distance queries in planar graphs
- Short and simple cycle separators in planar graphs
- 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
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)
