Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Applying clique-decomposition for computing Gromov hyperbolicity

Nathann Cohen 1 David Coudert 2, 3 Guillaume Ducoffe 4 Aurélien Lancin 2 
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The shortest-path metric d of a connected graph G is δ-hyperbolic if, and only if, it satisfies d(u, v)+d(x, y) ≤ max{d(u, x)+d(v, y), d(u, y)+d(v, x)}+2δ, for every 4-tuple u, x, v, y of G. We investigate some relations between the hyperbolicity of a graph and the hyperbolicity of its atoms, that are the subgraphs resulting from the clique-decomposition invented by Tarjan [34, 45]. More precisely, we prove that the maximum hyperbolicity taken over all the atoms is at least the hyperbolicity of G minus one. We also give an algorithm to slightly modify the atoms, which is at no extra cost than computing the atoms themselves, and so that the maximum hyperbolicity taken over all the resulting graphs is exactly the hyperbolicity of G. An experimental evaluation of our methodology is provided for large collaboration networks. Finally, we deduce from our theoretical results the first linear-time algorithm to compute the hyperbolicity of an outerplanar graph.
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Sunday, June 29, 2014 - 1:06:31 PM
Last modification on : Friday, October 28, 2022 - 3:28:33 AM
Long-term archiving on: : Monday, September 29, 2014 - 10:41:24 AM


Files produced by the author(s)


  • HAL Id : hal-00989024, version 2


Nathann Cohen, David Coudert, Guillaume Ducoffe, Aurélien Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. [Research Report] RR-8535, INRIA. 2014, pp.33. ⟨hal-00989024v2⟩



Record views


Files downloads