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

DOI10.1002/NET.20214MaRDI QIDQ3507648zbMATH OpenOpenAlexFDO

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

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 complexitydominating vertexedge contractiongraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The computational complexity of graph contractions II: Two tough polynomially solvable 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 Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Contraction theorems in Hamiltonian graph theory
• Graph minors. XIII: The disjoint paths problem
• Graph theory with applications
• Hierarchy of surface models and irreducible triangulations.
• scientific article; zbMATH DE number 2081091 (Why is no real title available?)
• On the NP-hardness of edge-deletion and -contraction problems
• Restricted Mesh Simplification Using Edge Contractions
• The computational complexity of graph contractions II: Two tough polynomially solvable cases

Cited in

(27)

• Modulo orientations and matchings in graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting induced star-like minors in polynomial time
• Increasing the minimum degree of a graph by contractions
• Edge contractions in subclasses of chordal graphs
• On contracting graphs to fixed pattern graphs
• Square contractions of graphs
• Graph contraction pattern matching for graphs of bounded treewidth
• Contractions of Planar Graphs in Polynomial Time
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Contractibility and NP-completeness
• Increasing the minimum degree of a graph by contractions
• Detecting induced minors in AT-free graphs
• On graph contractions and induced minors
• Edge contractions in subclasses of chordal graphs
• Theory-Contraction is NP-Complete
• Contracting chordal graphs and bipartite graphs to paths and trees
• The complexity of graph contractions.
• Contracting chordal graphs and bipartite graphs to paths and trees
• The complexity of contracting bipartite graphs into small cycles
• Contracting to a longest path in H-free graphs
• Contracting planar graphs to contractions of triangulations
• Finding maximum common contractions between phylogenetic networks
• The complexity of contracting bipartite graphs into small cycles
• Title not available (Why is no real title available?)
• Containment relations in split graphs
• Edge-contraction problems

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

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