New Bounds for Approximating Extremal Distances in Undirected Graphs - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

New Bounds for Approximating Extremal Distances in Undirected Graphs


We provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2−ε)-approximation of the diameter or a (5/3 − ε)-approximation of all the eccentricities in O(m 2−δ) time for any ε, δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 − 1/2 k)-approximation of the diameter and the radius and a (3 − 4/(2 k + 1))-approximation of all eccentricities in O(mn 1 k+1) expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h-dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter.
Fichier principal
Vignette du fichier
soda2016.pdf (454.12 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01526665 , version 1 (23-05-2017)



Massimo Cairo, Roberto Grossi, Romeo Rizzi. New Bounds for Approximating Extremal Distances in Undirected Graphs. SIAM: ACM-SIAM Symposium on Discrete Algorithms (SODA'16), Jan 2016, Arlington, United States. pp.363 - 376, ⟨10.1137/1.9781611974331.ch27⟩. ⟨hal-01526665⟩


107 View
396 Download



Gmail Facebook Twitter LinkedIn More