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

David Coudert 1 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
Abstract : 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014, 28 (3), pp.1601-1617. <10.1137/140954787>
Liste complète des métadonnées

https://hal.inria.fr/hal-01070768
Contributeur : David Coudert <>
Soumis le : jeudi 2 octobre 2014 - 11:51:19
Dernière modification le : lundi 5 octobre 2015 - 16:58:12
Document(s) archivé(s) le : samedi 3 janvier 2015 - 10:46:42

Fichier

CoDu14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Guillaume Ducoffe. Recognition of C4-free and 1/2-hyperbolic graphs. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014, 28 (3), pp.1601-1617. <10.1137/140954787>. <hal-01070768>

Partager

Métriques

Consultations de
la notice

197

Téléchargements du document

214