Parameterized complexity of three edge contraction problems with degree constraints
From MaRDI portal
Recommendations
- Parameterized Complexity of Two 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 edge dominating set in graphs with degree bounded by 3
- scientific article; zbMATH DE number 4202289
- Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
- Parameterized Complexity of Edge Interdiction Problems
- The computational complexity of three graph problems for instances with bounded minors of constraint matrices
- An extremal problem on contractible edges in 3-connected graphs
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
Cites work
- A 4k^2 kernel for feedback vertex set
- A generalization of Nemhauser and Trotter's local optimization theorem
- Chordal deletion is fixed-parameter tractable
- Contractibility and NP-completeness
- Contracting chordal graphs and bipartite graphs to paths and trees
- Contracting few edges to remove forbidden induced subgraphs
- Edge-contraction problems
- Edge-Deletion Problems
- Editing graphs to satisfy degree constraints: a parameterized approach
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Finding small separators in linear time via treewidth reduction
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Increasing the minimum degree of a graph by contractions
- Machine-based methods in parameterized complexity theory
- Non deterministic polynomial optimization problems and their approximations
- Obtaining a bipartite graph by contracting few edges
- Obtaining planarity by contracting few edges
- On the Amount of Nondeterminism and the Power of Verifying
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- On the structure of parameterized problems in NP
- Parameterized complexity of finding regular induced subgraphs
- Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
- Parameterizing cut sets in a graph by the number of their components
- Parametrized complexity theory.
- The node-deletion problem for hereditary properties is NP-complete
- The parameterized complexity of editing graphs for bounded degeneracy
Cited in
(24)- On the parameterized complexity of contraction to generalization of trees
- An improved linear kernel for the cycle contraction problem
- The complexity of degree anonymization by graph contractions
- On the parameterized complexity of grid contraction
- A single exponential-time FPT algorithm for cactus contraction
- Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
- Increasing the minimum degree of a graph by contractions
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Editing to a planar graph of given degrees
- Increasing the minimum degree of a graph by contractions
- On the parameterized complexity of contraction to generalization of trees
- Graph editing problems with extended regularity constraints
- Contracting to a longest path in H-free graphs
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- Reducing the vertex cover number via edge contractions
- Finding maximum common contractions between phylogenetic networks
- Revisiting path contraction and cycle contraction
- Revisiting path contraction and cycle contraction
- The complexity of contracting bipartite graphs into small cycles
- Editing to a planar graph of given degrees
- The parameterized landscape of labeled graph contractions
- A finer view of the parameterized landscape of labeled graph contractions
- On the parameterized complexity of maximum degree contraction problem
- Editing to Eulerian graphs
This page was built for publication: Parameterized complexity of three 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 Q471188)
