Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints

DOI10.1007/978-3-319-03898-8_3MaRDI QIDQ2867069zbMATH OpenOpenAlexFDO

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

Publication date 10 December 2013

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

Full work available at URL http://dro.dur.ac.uk/14198/1/14198.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)

Recommendations

• Parameterized complexity of three edge contraction problems with degree constraints
• On the parameterized complexity of maximum degree contraction problem
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Parameterized Complexity of Edge Interdiction Problems
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Parameterized complexity of finding small degree-constrained subgraphs
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• The parameterized complexity of the minimum shared edges problem

Cited in

(8)

• Parameterized Complexity of Edge Interdiction Problems
• An improved linear kernel for the cycle contraction problem
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Parameterized complexity of three edge contraction problems with degree constraints
• Obtaining split graphs by edge contraction
• On the parameterized complexity of maximum degree contraction problem
• Increasing the minimum degree of a graph by contractions
• Increasing the minimum degree of a graph by contractions

This page was built for publication: Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints

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