The kernelization complexity of connected domination in graphs with (no) small cycles
DOI10.1007/S00453-012-9681-ZzbMATH Open1318.68096OpenAlexW2083586074MaRDI QIDQ476436FDOQ476436
Authors: Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh 
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9681-z
Recommendations
- The effect of girth on the kernelization complexity of connected dominating set
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Perfect domination and small cycles
- Connectivity is not a limit for kernelization: planar connected dominating set
- Triangles, 4-Cycles and Parameterized (In-)Tractability
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Computational Complexity
- Graph minors. XX: Wagner's conjecture
- On problems without polynomial kernels
- Incompressibility through Colors and IDs
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Title not available (Why is that?)
- (Meta) Kernelization
- Bidimensionality and kernels
- Infeasibility of instance compression and succinct PCPs for NP
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Kernel bounds for disjoint cycles and disjoint paths
- Polynomial-time data reduction for dominating set
- Title not available (Why is that?)
- Domination problems in nowhere-dense classes of graphs
- Graph minors. VIII: A Kuratowski theorem for general surfaces
- Connectivity is not a limit for kernelization: planar connected dominating set
- Linear Kernel for Planar Connected Dominating Set
- The steiner problem in graphs
- An improved kernel for planar connected dominating set
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- A linear kernel for a planar connected dominating set
- Title not available (Why is that?)
- A simpler proof of the excluded minor theorem for higher surfaces
- The effect of girth on the kernelization complexity of connected dominating set
- On Problems without Polynomial Kernels (Extended Abstract)
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
Cited In (8)
- Smaller kernels for several FPT problems based on simple observations
- The effect of girth on the kernelization complexity of connected dominating set
- Perfect domination and small cycles
- On the lossy kernelization for connected treedepth deletion set
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Improved kernel results for some FPT problems based on simple observations
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
This page was built for publication: The kernelization complexity of connected domination in graphs with (no) small cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476436)
