A faster algorithm to recognize even-hole-free graphs

MaRDI QIDQ5743476zbMATH OpenFDO

Authors Hsien-Chih Chang, Hsueh-I Lu

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095217

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• A faster algorithm to recognize even-hole-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• Triangulated neighborhoods in even-hole-free graphs
• Finding a shortest even hole in polynomial time
• On the structure of (pan, even hole)-free graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for finding an induced cycle in planar graphs
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• Algorithms for Perfectly Contractile Graphs
• Bisimplicial vertices in even-hole-free graphs
• Combinatorial optimization with 2-joins
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• Detecting 2-joins faster
• Detecting a Theta or a Prism
• Detecting even holes
• Detecting holes and antiholes in graphs
• Even and odd holes in cap-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Even-hole-free graphs. I: Decomposition theorem
• Even-hole-free graphs: A survey
• Even-hole-free planar graphs have bounded treewidth
• Finding a smallest odd hole in a claw-free graph using global structure
• Hole and antihole detection in graphs
• scientific article; zbMATH DE number 3593613 (Why is no real title available?)
• scientific article; zbMATH DE number 1496606 (Why is no real title available?)
• Odd Hole Recognition in Graphs of Bounded Clique Size
• On diameters and radii of bridged graphs
• On the complexity of testing for odd holes and induced odd paths
• Recognizing Berge graphs
• Recognizing bull-free perfect graphs
• Recognizing claw-free perfect graphs
• Recognizing Dart-Free Perfect Graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Smallest odd holes in claw-free graphs (extended abstract)
• Star-cutsets and perfect graphs
• Testing for a theta
• The NP-completeness column
• The strong perfect graph theorem
• The three-in-a-tree problem
• Triangulated neighborhoods in even-hole-free graphs

Cited in

(11)

• On the structure of (even hole, kite)-free graphs
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• A faster algorithm to recognize even-hole-free graphs
• Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
• An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• Detecting even holes
• Odd Hole Recognition in Graphs of Bounded Clique Size
• Finding a shortest even hole in polynomial time
• Triangulated neighborhoods in even-hole-free graphs

This page was built for publication: A faster algorithm to recognize even-hole-free graphs

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