On the Parameterized Complexity of Maximum Degree Contraction Problem.
From MaRDI portal
Cites work
- 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
- scientific article; zbMATH DE number 1354124 (Why is no real title available?)
- Increasing the minimum degree of a graph by contractions
- Isolation concepts for efficiently enumerating dense subgraphs
- 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 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
- 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
(8)- A general framework for computing maximal contractions
- A decomposition based algorithm for maximal contractions
- On the parameterized complexity of grid contraction
- On the parameterized complexity of the Maximum Exposure Problem
- Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
- Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization
- 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 Q6089673)
