Faster Approximate Diameter and Distance Oracles in Planar Graphs
DOI10.4230/LIPICS.ESA.2017.25zbMATH Open1442.68262OpenAlexW2759043819MaRDI QIDQ5111711FDOQ5111711
Authors: 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/
Recommendations
- Faster approximate diameter and distance oracles in planar graphs
- Fast and Compact Oracles for Approximate Distances in Planar Graphs
- Approximating the diameter of planar graphs in near linear time
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Approximate distance oracles for planar graphs with improved query time-space tradeoff
- Almost optimal distance oracles for planar graphs
- Efficient dynamic approximate distance oracles for vertex-labeled planar graphs
- Efficient dynamic approximate distance oracles for vertex-labeled planar graphs
- More compact oracles for approximate distances in undirected planar graphs
- Better tradeoffs for exact distance oracles in planar graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
Cites Work
- Concrete and abstract Voronoi diagrams
- A Separator Theorem for Planar Graphs
- Randomized incremental construction of abstract Voronoi diagrams
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fast Algorithms for Finding Nearest Common Ancestors
- Maintaining information in fully dynamic trees with top trees
- Compact oracles for reachability and approximate distances in planar digraphs
- Faster shortest-path algorithms for planar graphs
- Computing the dilation of edge-augmented graphs in metric spaces
- Title not available (Why is that?)
- Faster Approximation of Distances in Graphs
- The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
- Multiple-source shortest paths in planar graphs
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Approximating the diameter of planar graphs in near linear time
- All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
- Title not available (Why is that?)
- More compact oracles for approximate distances in undirected planar graphs
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
Cited In (11)
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Planar diameter via metric compression
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Faster approximate diameter and distance oracles in planar graphs
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Title not available (Why is that?)
- Approximating the diameter of planar graphs in near linear time
- Fast and Compact Oracles for Approximate Distances in Planar Graphs
- Title not available (Why is that?)
- Almost optimal distance oracles for planar graphs
This page was built for publication: Faster Approximate Diameter and Distance Oracles in Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111711)
