Contracting a chordal graph to a split graph or a tree

DOI10.1007/978-3-642-22993-0_32MaRDI QIDQ3088052zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Marcin Kamiński, Daniël Paulusma

Publication date 17 August 2011

Published in Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22993-0_32

Mathematics Subject Classification ID

Graph minors (05C83) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Detecting fixed patterns in chordal graphs in polynomial time
• Edge contractions in subclasses of chordal graphs
• Edge contractions in subclasses of chordal graphs
• On graph contractions and induced minors
• Contracting chordal graphs and bipartite graphs to paths and trees

Cited in

(6)

• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting induced star-like minors in polynomial time
• Edge contractions in subclasses of chordal graphs
• Edge contractions in subclasses of chordal graphs
• The complexity of contracting bipartite graphs into small cycles
• Containment relations in split graphs

This page was built for publication: Contracting a chordal graph to a split graph or a tree

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