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 - e)-approximation of all the eccentricities in O(m2-δ) 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κ)-approximation of the diameter and the radius and a (3-4/(2k + 1))-approximation of all eccentricities in Ō (mn1/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.
New bounds for approximating extremal distances in undirected graphs
RIZZI, ROMEO
2016-01-01
Abstract
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 - e)-approximation of all the eccentricities in O(m2-δ) 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κ)-approximation of the diameter and the radius and a (3-4/(2k + 1))-approximation of all eccentricities in Ō (mn1/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.File | Dimensione | Formato | |
---|---|---|---|
newBoundsDiameter.pdf
solo utenti autorizzati
Tipologia:
Versione dell'editore
Licenza:
Accesso ristretto
Dimensione
237.23 kB
Formato
Adobe PDF
|
237.23 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.