A faster algorithm to recognize even-hole-free graphs
From MaRDI portal
Publication:2347846
DOI10.1016/j.jctb.2015.02.001zbMath1315.05107arXiv1311.0358OpenAlexW3103742520MaRDI QIDQ2347846
Publication date: 10 June 2015
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.0358
diamond2-jointrackerstar-cutsetbeetledecomposition-based detection algorithmeven holeextended clique tree
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Detecting a long even hole, Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree, A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\), Structure and algorithms for (cap, even hole)-free graphs, Finding a shortest even hole in polynomial time, On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs, Coloring \((4K_1,C_4,C_6)\)-free graphs, On the structure of (pan, even hole)‐free graphs, FPT and kernelization algorithms for the induced tree problem, Polyhedral properties of the induced cluster subgraphs, The Impact of Locality in the Broadcast Congested Clique Model
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The three-in-a-tree problem
- Algorithms for finding an induced cycle in planar graphs
- Combinatorial optimization with 2-joins
- The strong perfect graph theorem
- Detecting holes and antiholes in graphs
- Triangulated neighborhoods in even-hole-free graphs
- Bisimplicial vertices in even-hole-free graphs
- \(K_{4}\)-free graphs with no odd holes
- A bound on the treewidth of planar even-hole-free graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- On diameters and radii of bridged graphs
- Star-cutsets and perfect graphs
- On the complexity of testing for odd holes and induced odd paths
- Corrigendum to: On the complexity of testing for odd holes and induced odd paths
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
- Compositions for perfect graphs
- Detecting 2-joins faster
- Finding a smallest odd hole in a claw-free graph using global structure
- Decomposing Berge graphs and detecting balanced skew partitions
- Recognizing Berge graphs
- Even-hole-free graphs part I: Decomposition theorem
- K4-free graphs with no odd hole: Even pairs and the circular chromatic number
- Even-hole-free graphs part II: Recognition algorithm
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Complexity of clique-coloring odd-hole-free graphs
- Addendum: 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
- Even and odd holes in cap-free graphs
- Detecting even holes
- Even-hole-free graphs: A survey
- The NP-completeness column
- Algorithms for Perfectly Contractile Graphs
- Odd Hole Recognition in Graphs of Bounded Clique Size
- Smallest Odd Holes in Claw-Free Graphs (Extended Abstract)
