New Bounds for Approximating Extremal Distances in Undirected Graphs

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 − ε)-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.
Type de document :
Communication dans un congrès
SIAM: ACM-SIAM Symposium on Discrete Algorithms (SODA'16), Jan 2016, Arlington, United States. pp.363 - 376, 2016, 〈10.1137/1.9781611974331.ch27〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01526665
Contributeur : Marie-France Sagot <>
Soumis le : mardi 23 mai 2017 - 13:08:47
Dernière modification le : mercredi 11 avril 2018 - 01:55:26
Document(s) archivé(s) le : lundi 28 août 2017 - 17:46:51

Fichier

soda2016.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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, 2016, 〈10.1137/1.9781611974331.ch27〉. 〈hal-01526665〉

Partager

Métriques

Consultations de la notice

151

Téléchargements de fichiers

113