Better Approximation Algorithms for the Graph Diameter

DOI10.1137/1.9781611973402.78zbMath1421.68199OpenAlexW4214773521MaRDI QIDQ5384040

Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, Virginia Vassilevska Williams

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4044e2116d9b23bbb5fa18fa123f2090d2df0f48

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ A note on hardness of diameter approximation ⋮ On the complexity of computing treebreadth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate proof-labeling schemes ⋮ Succinct enumeration of distant vertex pairs ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Fast approximate shortest paths in the congested clique ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs