Edge Contractions in Subclasses of Chordal Graphs

DOI10.1007/978-3-642-20877-5_51zbMath1331.68097OpenAlexW1535551556MaRDI QIDQ3010431

Pim van 't Hof, Pinar Heggernes, Rémy Belmonte

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_51

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Increasing the Minimum Degree of a Graph by Contractions ⋮ Detecting induced star-like minors in polynomial time ⋮ Increasing the minimum degree of a graph by contractions ⋮ Edge contractions in subclasses of chordal graphs ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ Containment relations in split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• Threshold graphs and related topics
• Quasi-threshold graphs
• Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
• On Contracting Graphs to Fixed Pattern Graphs
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• Contractions of Planar Graphs in Polynomial Time
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Contractibility and NP-completeness
• The Comparability Graph of a Tree
• Graph Classes: A Survey
• A Note on "The Comparability Graph of a Tree"