Faster approximate diameter and distance oracles in planar graphs
From MaRDI portal
Publication:1999961
DOI10.1007/s00453-019-00570-zzbMath1425.68454OpenAlexW2939467540MaRDI QIDQ1999961
Dimitrios Skrepetos, Timothy M. Chan
Publication date: 27 June 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7838/
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 (3)
Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Shortest-Path Queries in Geometric Networks ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs
Cites Work
- Randomized incremental construction of abstract Voronoi diagrams
- How to draw a planar graph on a grid
- Computing the dilation of edge-augmented graphs in metric spaces
- Making data structures persistent
- Concrete and abstract Voronoi diagrams
- Surpassing the information theoretic bound with fusion trees
- Applications of random sampling in computational geometry. II
- A data structure for dynamic trees
- 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
- 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
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Faster Approximate Diameter and Distance Oracles in Planar Graphs
- Improved sparse covers for graphs excluding a fixed minor
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Faster approximate diameter and distance oracles in planar graphs
