Contracting chordal graphs and bipartite graphs to paths and trees

DOI10.1016/J.ENDM.2011.05.016MaRDI QIDQ5891098zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Pim Van 't Hof, Benjamin Lévêque, Paul Christophe

Publication date 23 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2011.05.016

zbMATH Keywords

chordal graphsedge contractionspolynomial time algorithms

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Contracting chordal graphs and bipartite graphs to paths and trees
• Edge contractions in subclasses of chordal graphs
• Contracting bipartite graphs to paths and cycles

Cites work

• A vertex incremental approach for maintaining chordality
• Algorithmic graph theory and perfect graphs
• Complexity classification of some edge modification problems
• Contractibility and NP-completeness
• Contractions of Planar Graphs in Polynomial Time
• Edge-contraction problems
• Finding induced subgraphs via minimal triangulations
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On contracting graphs to fixed pattern graphs
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The maximum k-colorable subgraph problem for chordal graphs

Cited in

(5)

• Increasing the minimum degree of a graph by contractions
• Increasing the minimum degree of a graph by contractions
• Contracting bipartite graphs to paths and cycles
• Contracting bipartite graphs to paths and cycles
• Contracting chordal graphs and bipartite graphs to paths and trees

This page was built for publication: Contracting chordal graphs and bipartite graphs to paths and trees

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