A linear kernel for a planar connected dominating set

DOI10.1016/j.tcs.2010.10.045zbMath1216.68131OpenAlexW2177196747MaRDI QIDQ534569

Matthias Mnich, Daniel Lokshtanov, Saket Saurabh

Publication date: 18 May 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.045

zbMATH Keywords

planar graphsconnected dominating setkernelizationreduce or refine

Mathematics Subject Classification ID

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

Related Items (max. 100)

Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ 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 ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Solving connected dominating set faster than \(2^n\)
• Approximation algorithms for connected dominating sets
• Vertex Cover: Further Observations and Further Improvements
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• A Linear Kernel for Planar Feedback Vertex Set
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
• Polynomial-time data reduction for dominating set
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor
• `` Strong NP-Completeness Results
• (Meta) Kernelization
• Bidimensionality and Geometric Graphs
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

This page was built for publication: A linear kernel for a planar connected dominating set