New Bounds for Approximating Extremal Distances in Undirected Graphs

DOI10.1137/1.9781611974331.ch27zbMath1410.68396OpenAlexW4230677477MaRDI QIDQ4575604

Massimo Cairo, Roberto Grossi, Romeo Rizzi

Publication date: 16 July 2018

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

Full work available at URL: https://hal.inria.fr/hal-01526665/file/soda2016.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Unnamed Item ⋮ A note on hardness of diameter approximation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Parameterized complexity of diameter ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

This page was built for publication: New Bounds for Approximating Extremal Distances in Undirected Graphs