Finding large holes

DOI10.1016/0020-0190(91)90184-JzbMath0735.68069OpenAlexW2062596745MaRDI QIDQ1182105

Jeremy P. Spinrad

Publication date: 27 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90184-j

zbMATH Keywords

holeschordless cyclesinduced pathweakly triangulated graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Algorithms for weakly triangulated graphs, A Dirac-type characterization of \(k\)-chordal graphs, Some problems on induced subgraphs, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, Disjoint clique cutsets in graphs without long holes, Maximum weight independent sets in hole- and dart-free graphs, An improved algorithm for the longest induced path problem on \(k\)-chordal graphs, Strong cliques in diamond-free graphs, Maximum weight independent sets in hole- and co-chair-free graphs, On stable cutsets in graphs

Cites Work

• Unnamed Item
• On rigid circuit graphs
• Topics on perfect graphs
• Weakly triangulated graphs
• A note on odd/even cycles
• Algorithms for weakly triangulated graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On Comparability and Permutation Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• `` Strong NP-Completeness Results