Connectivity is not a limit for kernelization: planar connected dominating set

DOI10.1007/978-3-642-12200-2_4MaRDI QIDQ3557006zbMATH OpenOpenAlexFDO

Authors Qian-Ping Gu, N. Imani

Publication date 27 April 2010

Published in LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-12200-2_4

Mathematics Subject Classification ID

Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A linear kernel for a planar connected dominating set
• Linear Kernel for Planar Connected Dominating Set
• Improved linear problem kernel for planar connected dominating set
• An improved kernel for planar connected dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs

Cited in

(13)

• Towards optimal kernel for connected vertex cover in planar graphs
• The effect of girth on the kernelization complexity of connected dominating set
• An improved kernel for planar connected dominating set
• New analysis and computational study for the planar connected dominating set problem
• Smaller kernels for several FPT problems based on simple observations
• Planar graph vertex partition for linear problem kernels
• Improved linear problem kernel for planar connected dominating set
• The kernelization complexity of connected domination in graphs with (no) small cycles
• Improved kernel results for some FPT problems based on simple observations
• A linear kernel for planar red-blue dominating set
• A linear kernel for a planar connected dominating set
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs

This page was built for publication: Connectivity is not a limit for kernelization: planar connected dominating set

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