Faster Approximate Diameter and Distance Oracles in Planar Graphs
From MaRDI portal
Publication:5111711
DOI10.4230/LIPIcs.ESA.2017.25zbMath1442.68262OpenAlexW2759043819MaRDI QIDQ5111711
Timothy M. Chan, Dimitrios Skrepetos
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7838/pdf/LIPIcs-ESA-2017-25.pdf/
Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Randomized incremental construction of abstract Voronoi diagrams
- Computing the dilation of edge-augmented graphs in metric spaces
- Concrete and abstract Voronoi diagrams
- Maintaining information in fully dynamic trees with top trees
- Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
- All-pairs shortest paths for unweighted undirected graphs in o ( mn ) time
- Fast Algorithms for Finding Nearest Common Ancestors
- Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
- Faster Approximation of Distances in Graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Approximating the Diameter of Planar Graphs in Near Linear Time
- 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
