Edge contractions in subclasses of chordal graphs
From MaRDI portal
Publication:423902
DOI10.1016/j.dam.2011.12.012zbMath1243.05225OpenAlexW2086859323MaRDI QIDQ423902
Pinar Heggernes, Rémy Belmonte, Pim van 't Hof
Publication date: 30 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.12.012
Related Items (5)
The micro-world of cographs ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Characterizations of cographs as intersection graphs of paths on a grid ⋮ Contracting chordal graphs and bipartite graphs to paths and trees
Cites Work
- Containment relations in split graphs
- 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
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Edge Contractions in Subclasses of Chordal Graphs
- Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
- Contracting a Chordal Graph to a Split Graph or a Tree
- Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
- 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"
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Edge contractions in subclasses of chordal graphs
