The kernelization complexity of connected domination in graphs with (no) small cycles

DOI10.1007/S00453-012-9681-ZMaRDI QIDQ476436zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

fixed-parameter tractabilitygirthkernelizationconnected dominating setkernel lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

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

Cites work

• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• (Meta) Kernelization
• A linear kernel for a planar connected dominating set
• A simpler proof of the excluded minor theorem for higher surfaces
• An improved kernel for planar connected dominating set
• Bidimensionality and kernels
• Computational Complexity
• Connectivity is not a limit for kernelization: planar connected dominating set
• Domination problems in nowhere-dense classes of graphs
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Graph minors. XX: Wagner's conjecture
• Incompressibility through Colors and IDs
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Linear Kernel for Planar Connected Dominating Set
• On Problems without Polynomial Kernels (Extended Abstract)
• On problems without polynomial kernels
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Polynomial-time data reduction for dominating set
• Reducibility among combinatorial problems
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• The effect of girth on the kernelization complexity of connected dominating set
• The steiner problem in graphs

Cited in

(8)

• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• On the lossy kernelization for connected treedepth deletion set
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• Smaller kernels for several FPT problems based on simple observations
• Improved kernel results for some FPT problems based on simple observations
• The effect of girth on the kernelization complexity of connected dominating set
• Perfect domination and small cycles

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)