On the parameterized complexity of maximum degree contraction problem
From MaRDI portal
Recommendations
- Parameterized complexity of three edge contraction problems with degree constraints
- Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
- Increasing the minimum degree of a graph by contractions
- Increasing the minimum degree of a graph by contractions
- On the parameterized complexity of grid contraction
Cites work
- A 4k^2 kernel for feedback vertex set
- A generalization of Nemhauser and Trotter's local optimization theorem
- A linear kernel for co-path/cycle packing
- An FPT algorithm for contraction to cactus
- Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes
- Color-coding
- Contractibility and NP-completeness
- Contracting few edges to remove forbidden induced subgraphs
- Edge-contraction problems
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 1354124 (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
- Isolation concepts for efficiently enumerating dense subgraphs
- Kernelization. Theory of parameterized preprocessing
- Lossy kernelization
- Lossy kernels for graph contraction problems
- Obtaining a bipartite graph by contracting few edges
- Obtaining planarity by contracting few edges
- On bounded-degree vertex deletion parameterized by treewidth
- On structural parameterizations of the bounded-degree vertex deletion problem
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- On the NP-hardness of edge-deletion and -contraction problems
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- On the parameterized approximability of contraction to classes of chordal graphs
- On the parameterized complexity of contraction to generalization of trees
- On the Parameterized Complexity Of Grid Contraction
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Parameterized algorithms
- Parameterized complexity of three edge contraction problems with degree constraints
- Parametrized complexity theory.
- Path contraction faster than 2ⁿ
- Paths to trees and cacti
- Reduction algorithms for graphs of small treewidth
- Slightly superexponential parameterized problems
- Split contraction: the untold story
- The computational complexity of disconnected cut and \(2 K_2\)-partition
Cited in
(10)- A general framework for computing maximal contractions
- A decomposition based algorithm for maximal contractions
- On the parameterized complexity of the Maximum Exposure Problem
- A single exponential-time FPT algorithm for cactus contraction
- Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
- Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization
- Increasing the minimum degree of a graph by contractions
- Increasing the minimum degree of a graph by contractions
- Parameterized complexity of three edge contraction problems with degree constraints
- Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)
This page was built for publication: On the parameterized complexity of maximum degree contraction problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832521)
