Parameterized complexity of three edge contraction problems with degree constraints

DOI10.1007/s00236-014-0204-zzbMath1360.68489OpenAlexW2003852880MaRDI QIDQ471188

Daniël Paulusma, Petr A. Golovach, Rémy Belmonte, Pim van 't Hof

Publication date: 14 November 2014

Published in: Acta Informatica (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph operations (line graphs, products, etc.) (05C76)

Related Items (15)

On the parameterized complexity of maximum degree contraction problem ⋮ Editing to a Planar Graph of Given Degrees ⋮ The complexity of degree anonymization by graph contractions ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ Editing to Eulerian graphs ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Graph editing problems with extended regularity constraints ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ An improved linear kernel for the cycle contraction problem ⋮ Editing to a planar graph of given degrees ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Increasing the minimum degree of a graph by contractions
• Editing graphs to satisfy degree constraints: a parameterized approach
• Machine-based methods in parameterized complexity theory
• Parameterizing cut sets in a graph by the number of their components
• A generalization of Nemhauser and Trotter's local optimization theorem
• Edge-contraction problems
• Chordal deletion is fixed-parameter tractable
• The parameterized complexity of editing graphs for bounded degeneracy
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding regular induced subgraphs
• The node-deletion problem for hereditary properties is NP-complete
• Non deterministic polynomial optimization problems and their approximations
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Obtaining planarity by contracting few edges
• Contracting graphs to paths and trees
• A faster FPT algorithm for bipartite contraction
• Parametrized complexity theory.
• On the structure of parameterized problems in NP
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Contracting Few Edges to Remove Forbidden Induced Subgraphs
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Finding small separators in linear time via treewidth reduction
• Contractibility and NP-completeness
• Edge-Deletion Problems
• On the Amount of Nondeterminism and the Power of Verifying
• Obtaining a Bipartite Graph by Contracting Few Edges
• Contracting chordal graphs and bipartite graphs to paths and trees

This page was built for publication: Parameterized complexity of three edge contraction problems with degree constraints