Applying clique-decomposition for computing Gromov hyperbolicity

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 metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/hal-00989024
Contributor : David Coudert <>
Submitted on : Sunday, June 29, 2014 - 1:06:31 PM
Last modification on : Thursday, February 7, 2019 - 4:19:25 PM
Long-term archiving on : Monday, September 29, 2014 - 10:41:24 AM

File

RR-8535-v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00989024, version 2

Citation

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⟩

Share

Metrics

Record views

717

Files downloads

416