Edge contractions in subclasses of chordal graphs

DOI10.1007/978-3-642-20877-5_51MaRDI QIDQ3010431zbMATH OpenOpenAlexFDO

Authors Rémy Belmonte, Pinar Heggernes, Pim Van 't Hof

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)

Recommendations

• Edge contractions in subclasses of chordal graphs
• On contracting graphs to fixed pattern graphs
• Contracting chordal graphs and bipartite graphs to paths and trees
• Detecting fixed patterns in chordal graphs in polynomial time
• Contracting a chordal graph to a split graph or a tree

Cites work

• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 139780 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A Note on "The Comparability Graph of a Tree"
• Algorithmic graph theory and perfect graphs
• Contractibility and NP-completeness
• Contractions of Planar Graphs in Polynomial Time
• Graph Classes: A Survey
• Graph minors. XIII: The disjoint paths problem
• Induced subgraph isomorphism on interval and proper interval graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On contracting graphs to fixed pattern graphs
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Quasi-threshold graphs
• The Comparability Graph of a Tree
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Threshold graphs and related topics

Cited in

(13)

• Contracting chordal graphs and bipartite graphs to paths and trees
• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting induced star-like minors in polynomial time
• Edge contractions in subclasses of chordal graphs
• Containment relations in split graphs
• Necessary edges in k-chordalisations of graphs
• Contracting a chordal graph to a split graph or a tree
• Increasing the minimum degree of a graph by contractions
• Increasing the minimum degree of a graph by contractions
• Contracting planar graphs to contractions of triangulations
• Contractibility and NP-completeness
• Contracting chordal graphs and bipartite graphs to paths and trees
• The complexity of blocking (semi)total dominating sets with edge contractions

This page was built for publication: Edge contractions in subclasses of chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010431)