New interface

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

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 $\frac{1}{2}$-hyperbolic if, and only if, it satisfies $d(u,v) + d(x,y) \leq \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 $\frac{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 :
Reports (Research report)

Cited literature [40 references]

https://hal.inria.fr/hal-00937935
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Tuesday, July 22, 2014 - 3:26:41 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:25 AM
Long-term archiving on: : Tuesday, April 11, 2017 - 4:15:41 PM

### File

RR-8458v2.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00937935, version 2

### 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⟩

Record views