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

DOI10.1137/140954787MaRDI QIDQ2935290zbMATH OpenOpenAlexFDO

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

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)

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?

Cited in

(18)

• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• The hyperbolicity constant of infinite circulant graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Fast approximation and exact computation of negative curvature parameters of graphs
• Gromov hyperbolicity in Mycielskian graphs
• When can graph hyperbolicity be computed in linear time?
• 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

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)