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

DOI10.1002/NET.20249MaRDI QIDQ3632967zbMATH OpenOpenAlexFDO

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

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

graphcomputational complexitywheeledge 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)

Recommendations

• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The complexity of graph contractions.
• On contracting graphs to fixed pattern graphs
• Contractibility and NP-completeness
• On graph contractions and induced minors

Cites work

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

Cited in

(20)

• Detecting fixed patterns in chordal graphs in polynomial time
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Detecting induced star-like minors in polynomial time
• Edge contractions in subclasses of chordal graphs
• Containment relations in split graphs
• Square contractions of graphs
• On contracting graphs to fixed pattern graphs
• Increasing the minimum degree of a graph by contractions
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• Contractions of Planar Graphs in Polynomial Time
• Increasing the minimum degree of a graph by contractions
• Detecting induced minors in AT-free graphs
• On graph contractions and induced minors
• Contracting to a longest path in H-free graphs
• Contracting planar graphs to contractions of triangulations
• Contractibility and NP-completeness
• Contracting chordal graphs and bipartite graphs to paths and trees
• The complexity of graph contractions.
• Graph contraction pattern matching for graphs of bounded treewidth
• Edge contractions in subclasses of chordal graphs

This page was built for publication: The computational complexity of graph contractions II: Two tough polynomially solvable cases

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