Finding a shortest even hole in polynomial time
From MaRDI portal
Publication:6057650
DOI10.1002/jgt.22748zbMath1523.68048arXiv2008.06740MaRDI QIDQ6057650
Publication date: 5 October 2023
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.06740
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time algorithm for the induced disjoint paths problem in planar graphs
- The three-in-a-tree problem
- The strong perfect graph theorem
- Triangulated neighborhoods in even-hole-free graphs
- Bisimplicial vertices in even-hole-free graphs
- 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 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
- A note on chromatic number of (cap, even hole)-free graphs
- Even pairs and prism corners in square-free Berge graphs
- On the structure of (even hole, kite)-free graphs
- Corrigendum to: ``Even pairs and prism corners in square-free Berge graphs
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
- Corrigendum to: ``Bisimplicial vertices in even-hole-free graphs
- Dense induced bipartite subgraphs in triangle-free graphs
- Detecting a long odd hole
- The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
- Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
- A faster algorithm to recognize even-hole-free graphs
- Recognizing Berge graphs
- FPT and kernelization algorithms for the induced tree problem
- Induced paths in 5-connected graphs
- Even-hole-free graphs part I: Decomposition theorem
- Even-hole-free graphs part II: Recognition algorithm
- Detecting a Theta or a Prism
- Detecting even holes
- Even-hole-free graphs: A survey
- The NP-completeness column
- Detecting an induced subdivision of K4
- Finding a Shortest Odd Hole
- Detecting an Odd Hole
- Three-in-a-tree in near linear time
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- Algorithms for Perfectly Contractile Graphs
- On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
