The complexity of graph contractions.

DOI10.1007/B93953MaRDI QIDQ5902532zbMATH OpenFDO

Authors Asaf Levin, Daniël Paulusma, Gerhard J. Woeginger

Publication date 12 January 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/B93953

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

• 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
• On contracting graphs to fixed pattern graphs
• Contractibility and NP-completeness
• On graph contractions and induced minors

Cited in

(12)

• A note on contracting claw-free graphs
• The complexity of contracting bipartite graphs into small cycles
• Square contractions of graphs
• On contracting graphs to fixed pattern graphs
• Subexponential parameterized algorithms
• The isomorphism problem for classes of graphs closed under contraction
• 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
• On graph contractions and induced minors
• Contractibility and NP-completeness
• Graph contraction pattern matching for graphs of bounded treewidth

This page was built for publication: The complexity of graph contractions.

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