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

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) 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)

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

• scientific article; zbMATH DE number 3593613 (Why is no real title available?)
• scientific article; zbMATH DE number 1496606 (Why is no real title available?)
• scientific article; zbMATH DE number 7051285 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Perfectly Contractile Graphs
• Algorithms for finding an induced cycle in planar 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
• 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 Dart-Free Perfect Graphs
• Recognizing bull-free perfect graphs
• Recognizing claw-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)

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

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)