Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
From MaRDI portal
Publication:3557006
DOI10.1007/978-3-642-12200-2_4zbMath1283.05149MaRDI QIDQ3557006
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
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C40: Connectivity
Related Items
Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems, New analysis and computational study for the planar connected dominating set problem, 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, An Improved Kernel for Planar Connected Dominating Set, Smaller Kernels for Several FPT Problems Based on Simple Observations