Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs

DOI10.1137/140954787zbMath1306.05233OpenAlexW1977820238MaRDI QIDQ2935290

David Coudert, Guillaume Ducoffe

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140954787

zbMATH Keywords

hyperbolicitygraph algorithmsdiscrete metric spacerectangular matrix multiplication\(\mathrm C_4\)-free graphs

Mathematics Subject Classification ID

Related Items (17)

The hyperbolicity constant of infinite circulant graphs ⋮ Obstructions to a small hyperbolicity in Helly graphs ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ On the hyperbolicity of bipartite graphs and intersection graphs ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ Fast approximation and exact computation of negative curvature parameters of graphs ⋮ On a classical theorem on the diameter and minimum degree of a graph ⋮ Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant ⋮ On the hyperbolicity constant of circular-arc graphs ⋮ On the hyperbolicity of random graphs ⋮ Gromov hyperbolicity in the Cartesian sum of graphs ⋮ To Approximate Treewidth, Use Treelength! ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ On Computing the Gromov Hyperbolicity ⋮ Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs ⋮ Gromov hyperbolicity in Mycielskian graphs

This page was built for publication: Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs