Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
From MaRDI portal
Publication:4629989
DOI10.1145/3218821zbMath1443.68122arXiv1702.07815OpenAlexW2903797494WikidataQ128829698 ScholiaQ128829698MaRDI QIDQ4629989
Publication date: 28 March 2019
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.07815
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 (16)
Medians in median graphs and their cube complexes in linear time ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Better distance labeling for unweighted planar graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Eccentricity queries and beyond using hub labels ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Continuous mean distance of a weighted graph ⋮ The diameter of AT‐free graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Better distance labeling for unweighted planar graphs ⋮ Compact distributed certification of planar graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
This page was built for publication: Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
