Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
From MaRDI portal
Publication:5858646
DOI10.1137/18M1193402OpenAlexW3140470499MaRDI QIDQ5858646
Paweł Gawrychowski, Shay Mozes, Oren Weimann, Haim Kaplan, Micha Sharir
Publication date: 14 April 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1193402
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Parameterized complexity of diameter
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On dynamic shortest paths problems
- Randomized incremental construction of abstract Voronoi diagrams
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Abstract Voronoi diagrams revisited
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- Geometric applications of a matrix-searching algorithm
- Computation of the center and diameter of outerplanar graphs
- Concrete and abstract Voronoi diagrams
- A new upper bound on the complexity of the all pairs shortest path problem
- Which problems have strongly exponential complexity?
- Applications of random sampling in computational geometry. II
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Efficient algorithms for center problems in cactus networks
- Improved algorithm for all pairs shortest paths
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Maintaining Minimum Spanning Forests in Dynamic Graphs
- Finding, Minimizing, and Counting Weighted Subgraphs
- Multiple-Source Shortest Paths in Embedded Graphs
- An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- COMPUTING THE MAXIMUM DETOUR OF A PLANE GEOMETRIC GRAPH IN SUBQUADRATIC TIME
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- A simple linear-time algorithm for computing the center of an interval graph
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- Shortest Cut Graph of a Surface with Prescribed Vertex Set
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
- Matrix Searching with the Shortest-Path Metric
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Tight Hardness Results for Maximum Weight Rectangles
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Computing Graph Distances Parameterized by Treewidth and Diameter
- Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
- Almost optimal distance oracles for planar graphs
- Holiest minimum-cost paths and flows in surface graphs
- Faster all-pairs shortest paths via circuit complexity
- Exact Weight Subgraphs and the k-Sum Conjecture
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Structured recursive separator decompositions for planar graphs in linear time
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Algorithms and Computation
- A Theorem on Boolean Matrices
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
