Applying clique-decomposition for computing Gromov hyperbolicity

Résumé : La métrique d des plus courts chemins d'un graphe connexe G est δ-hyperbolique si, et seulement si, elle satisfait d(u, v) + d(x, y) ≤ max{d(u, x) + d(v, y), d(u, y) + d(v, x)} + 2δ, pour tout quadruplet u, x, v, y de G. Nous étudions la relation entre l'hyperbolicité d'un graphe et celle de chacun de ses atomes. Ces derniers sont les sous-graphes résultant de la décomposition d'un graphe par des cliques-séparatrices [34, 45]. Plus précisemment, nous montrons que l'hyperbolicité d'un atome est au plus l'hyperbolicité de G moins un. Nous proposons un algorithme pour modifier les atomes de sorte que la valeur maximale de l'hyperbolicité de ces atomes modifiés soit exactement l'hyperbolicité de G. La complexité de cet algorithme est la même que celle de la décomposition du graphe par des cliques-séparatrices. Nous évaluons expériementalement cette méthode sur des graphes de collaborations (co-auteurs). Enfin, nous proposons un algorithme pour calculer en temps linéaire l'hyperbolicité des graphes planaires extérieurs.
Type de document :
Rapport
[Research Report] RR-8535, INRIA. 2014, pp.33


https://hal.inria.fr/hal-00989024
Contributeur : David Coudert <>
Soumis le : dimanche 29 juin 2014 - 13:06:31
Dernière modification le : jeudi 9 février 2017 - 15:30:31
Document(s) archivé(s) le : lundi 29 septembre 2014 - 10:41:24

Fichier

RR-8535-v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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>

Partager

Métriques

Consultations de
la notice

410

Téléchargements du document

198