Contracting chordal graphs and bipartite graphs to paths and trees

DOI10.1016/J.ENDM.2011.05.016zbMATH Open1268.05201OpenAlexW4252125530MaRDI QIDQ5891098FDOQ5891098

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

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

Recommendations

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

zbMATH Keywords

chordal graphspolynomial time algorithmsedge contractions

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Finding Induced Subgraphs via Minimal Triangulations
• Complexity classification of some edge modification problems
• Contracting graphs to paths and trees
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• Contractions of Planar Graphs in Polynomial Time
• Contractibility and NP-completeness
• Edge-contraction problems
• A vertex incremental approach for maintaining chordality
• On Contracting Graphs to Fixed Pattern Graphs

Cited In (4)

• Increasing the Minimum Degree of a Graph by Contractions
• Increasing the minimum degree of a graph by contractions
• Contracting chordal graphs and bipartite graphs to paths and trees
• Contracting 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)