Recognition of C4-free and 1/2-hyperbolic graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2014

Recognition of C4-free and 1/2-hyperbolic graphs

Résumé

The shortest-path metric d of a connected graph G is 1/2-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)} + 1, for every 4-tuple u,x,v,y of G. We show that the problem of deciding whether an unweighted graph is 1/2-hyperbolic is subcubic equivalent to the problem of determining whether there is a chordless cycle of length 4 in a graph. An improved algorithm is also given for both problems, taking advantage of fast rectangular matrix multiplication. In the worst case it runs in O(n^{3.26})-time.
Fichier principal
Vignette du fichier
CoDu14.pdf (431.86 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01070768 , version 1 (02-10-2014)

Identifiants

Citer

David Coudert, Guillaume Ducoffe. Recognition of C4-free and 1/2-hyperbolic graphs. SIAM Journal on Discrete Mathematics, 2014, 28 (3), pp.1601-1617. ⟨10.1137/140954787⟩. ⟨hal-01070768⟩
179 Consultations
342 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More