Recognition of C₄-free and 1/2-hyperbolic graphs

DOI10.1137/140954787zbMATH Open1306.05233OpenAlexW1977820238MaRDI QIDQ2935290FDOQ2935290

Authors: 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

Recommendations

• 1-Hyperbolic Graphs
• Hyperbolicity and chordality of a graph
• On the hyperbolicity of chordal graphs
• Chordality properties and hyperbolicity on graphs
• When can graph hyperbolicity be computed in linear time?

zbMATH Keywords

graph algorithmshyperbolicitydiscrete metric spacerectangular matrix multiplication\(\mathrm C_4\)-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (18)

• The hyperbolicity constant of infinite circulant graphs
• Fast approximation and exact computation of negative curvature parameters of graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• When can graph hyperbolicity be computed in linear time?
• Gromov hyperbolicity in Mycielskian graphs
• Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant
• Obstructions to a small hyperbolicity in Helly graphs
• Gromov hyperbolicity in the Cartesian sum of graphs
• On a classical theorem on the diameter and minimum degree of a graph
• On the hyperbolicity constant of circular-arc graphs
• On the hyperbolicity of random 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
• To approximate treewidth, use treelength!
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• On computing the Gromov hyperbolicity
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs

This page was built for publication: Recognition of \(C_4\)-free and \(1/2\)-hyperbolic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2935290)