The effect of girth on the kernelization complexity of connected dominating set

DOI10.4230/LIPICS.FSTTCS.2010.96MaRDI QIDQ2908840zbMATH OpenFDO

Authors Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh

Publication date 29 August 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_f71a.html

zbMATH Keywords

connected dominating setgirthkernelizationparameterized complexity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The kernelization complexity of connected domination in graphs with (no) small cycles
• Connectivity is not a limit for kernelization: planar connected dominating set
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Kernels for (connected) dominating set on graphs with excluded topological minors
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs

Cited in

(5)

• Kernelization and Sparseness: the case of Dominating Set
• The kernelization complexity of connected domination in graphs with (no) small cycles
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Perfect domination and small cycles
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

This page was built for publication: The effect of girth on the kernelization complexity of connected dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908840)