On the recognition of $C_4$-free and $1/2$-hyperbolic graphs

David Coudert 1, 2 Guillaume Ducoffe 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : La métrique $d$ des plus courts chemins d'un graphe connexe $G$ est $\frac{1}{2}$-hyperbolique si et seulement si elle satisfait $d(u,v) + d(x,y) \leq \max \{ d(u,x) + d(v,y), d(u,y) + d(v,x) \} + 1$ pour tout quadruplet $u,x,v,y$ de $G$. Nous montrons que résoudre le problème de décider si un graphe est $1/2$-hyperbolique revient à résoudre le problème de décider si un graphe contient un cycle sans corde de longueur 4, et inversement, en proposant une transformation en temps sous-cubique d'un problème vers l'autre. De plus, nous proposons un algorithme en temps $O(n^{3.26})$, basé sur la multiplication de matrices rectangulaires, pour résoudre chacun de ces problèmes. Nous améliorons ainsi l'état de l'art.
Type de document :
Rapport
[Research Report] RR-8458, INRIA. 2014, pp.20
Liste complète des métadonnées


https://hal.inria.fr/hal-00937935
Contributeur : David Coudert <>
Soumis le : mardi 22 juillet 2014 - 15:26:41
Dernière modification le : vendredi 16 septembre 2016 - 15:21:16
Document(s) archivé(s) le : mardi 11 avril 2017 - 16:15:41

Fichier

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

Identifiants

  • HAL Id : hal-00937935, version 2

Collections

Citation

David Coudert, Guillaume Ducoffe. On the recognition of $C_4$-free and $1/2$-hyperbolic graphs. [Research Report] RR-8458, INRIA. 2014, pp.20. <hal-00937935v2>

Partager

Métriques

Consultations de
la notice

346

Téléchargements du document

229