Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
DOI10.1007/978-3-319-03898-8_3zbMATH Open1360.68488OpenAlexW194907680MaRDI QIDQ2867069FDOQ2867069
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
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph operations (line graphs, products, etc.) (05C76)
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
- Increasing the minimum degree of a graph by contractions
- On the parameterized complexity of maximum degree contraction problem
- 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)
