Publication:5743390
From MaRDI portal
zbMath1422.68053arXiv1011.5549MaRDI QIDQ5743390
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1011.5549
05C10: Planar graphs; geometric and topological aspects of graph theory
05C12: Distance in graphs
68P05: Data structures
68P20: Information storage and retrieval of data
Related Items
Short and Simple Cycle Separators in Planar Graphs, Unnamed Item, A substring-substring LCS data structure, Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Computing the dilation of edge-augmented graphs in metric spaces
- Finding small simple cycle separators for 2-connected planar graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Graph minors. X: Obstructions to tree-decomposition
- S-functions for graphs
- Call routing and the ratcatcher
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- Diameter and treewidth in minor-closed graph families
- Improved algorithms for dynamic shortest paths
- Diameter and treewidth in minor-closed graph families, revisited
- An external memory data structure for shortest path queries
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Shortest paths in directed planar graphs with negative lengths
- Oracles for bounded-length shortest paths in planar graphs
- Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
- Compact Navigation and Distance Oracles for Graphs with Small Treewidth
- VC-Dimension and Shortest Path Algorithms
- Fast Routing in Road Networks with Transit Nodes
- Shortest path queries in planar graphs
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Preprocessing Speed-Up Techniques Is Hard
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- The Shortcut Problem – Complexity and Approximation
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Graph minors. II. Algorithmic aspects of tree-width
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Efficient Algorithms for Shortest Paths in Sparse Networks
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Approximation algorithms for NP-complete problems on planar graphs
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- Distance Oracles for Sparse Graphs
- Improved Distance Queries in Planar Graphs
- Distance Oracles beyond the Thorup--Zwick Bound
- Compact oracles for reachability and approximate distances in planar digraphs
- Algorithms – ESA 2005
- Experimental and Efficient Algorithms
- Algorithms and Computation
- Many distances in planar graphs
- Faster shortest-path algorithms for planar graphs
