Increasing the Minimum Degree of a Graph by Contractions

DOI10.1007/978-3-642-28050-4_6zbMath1352.68106OpenAlexW1913947078MaRDI QIDQ2891338

Daniël Paulusma, Petr A. Golovach, Marcin Kaminski, Dimitrios M. Thilikos

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/10711/1/10711.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Contracting graphs to paths and trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of finding small degree-constrained subgraphs
• On graph contractions and induced minors
• Edge-contraction problems
• On the parameterized complexity of multiple-interval graph problems
• Partitioning graphs into connected parts
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• On the NP-hardness of edge-deletion and -contraction problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Edge Contractions in Subclasses of Chordal Graphs
• Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
• 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
• Contractibility and NP-completeness
• Contraction and Treewidth Lower Bounds
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Contracting chordal graphs and bipartite graphs to paths and trees