The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases

DOI10.1002/net.20214zbMath1140.68025OpenAlexW4234850175MaRDI QIDQ3507648

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

Publication date: 20 June 2008

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20214

zbMATH Keywords

computational complexitygraphedge contractiondominating vertex

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Increasing the Minimum Degree of a Graph by Contractions ⋮ Modulo orientations and matchings in graphs ⋮ Detecting induced star-like minors in polynomial time ⋮ Increasing the minimum degree of a graph by contractions ⋮ Detecting induced minors in AT-free graphs ⋮ The complexity of contracting bipartite graphs into small cycles ⋮ On graph contractions and induced minors ⋮ Edge contractions in subclasses of chordal graphs ⋮ Contracting planar graphs to contractions of triangulations ⋮ Edge Contractions in Subclasses of Chordal Graphs ⋮ Contracting to a longest path in H-free graphs ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ The computational complexity of graph contractions II: Two tough polynomially solvable cases ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Containment relations in split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Contraction theorems in Hamiltonian graph theory
• Hierarchy of surface models and irreducible triangulations.
• On the NP-hardness of edge-deletion and -contraction problems
• Graph minors. XIII: The disjoint paths problem
• Restricted Mesh Simplification Using Edge Contractions
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

This page was built for publication: The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases