Fast approximation algorithms for the diameter and radius of sparse graphs

DOI10.1145/2488608.2488673zbMath1293.05184OpenAlexW2047489708MaRDI QIDQ5495822

Liam Roditty, Virginia Vassilevska Williams

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2488608.2488673

zbMATH Keywords

approximation algorithmshortest pathsgraph diameter

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Approximation algorithms (68W25)

Related Items (61)

Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ A note on the complexity of computing the number of reachable vertices in a digraph ⋮ Eccentricity queries and beyond using hub labels ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ Continuous mean distance of a weighted graph ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ The diameter of AT‐free graphs ⋮ Unnamed Item ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Computing and listing avoidable vertices and paths ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Interpretable random forest model for identification of edge 3-uncolorable cubic graphs ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ Computing and listing avoidable vertices and paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Unnamed Item ⋮ A note on hardness of diameter approximation ⋮ Hardness of RNA folding problem with four symbols ⋮ Parsimonious formulations for low-diameter clusters ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate proof-labeling schemes ⋮ Compact distributed certification of planar graphs ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Unnamed Item ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Parameterized complexity of diameter ⋮ Unnamed Item ⋮ Computing Giant Graph Diameters ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Fast approximate shortest paths in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multivariate analysis of orthogonal range searching and graph distances ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Unnamed Item ⋮ Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs ⋮ Fast Diameter Computation within Split Graphs

This page was built for publication: Fast approximation algorithms for the diameter and radius of sparse graphs