The computational complexity of graph contractions II: Two tough polynomially solvable cases

DOI10.1002/net.20249zbMath1182.05118OpenAlexW4235091083MaRDI QIDQ3632967

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

Publication date: 16 June 2009

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraphwheeledge contractiondominating vertex

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Related Items

Increasing the Minimum Degree of a Graph by Contractions, 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 computational complexity of graph contractions I: Polynomially solvable and NP-complete cases, 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, Containment relations in split graphs

Cites Work

• Unnamed Item
• Graph minors. XIII: The disjoint paths problem
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• A Polynomial Solution to the Undirected Two Paths Problem