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