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 , Laboratoire I3S - 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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-01070768
Contributor : David Coudert <>
Submitted on : Thursday, October 2, 2014 - 11:51:19 AM
Last modification on : Friday, April 19, 2019 - 11:12:03 AM
Document(s) archivé(s) le : Saturday, January 3, 2015 - 10:46:42 AM

File

CoDu14.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

340

Files downloads

327