Edge contractions in subclasses of chordal graphs
From MaRDI portal
Publication:423902
DOI10.1016/j.dam.2011.12.012zbMath1243.05225MaRDI 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
Contracting chordal graphs and bipartite graphs to paths and trees, Induced subgraph isomorphism on proper interval and bipartite permutation graphs, Characterizations of cographs as intersection graphs of paths on a grid, The micro-world of cographs, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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"
