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