Linear Kernel for Planar Connected Dominating Set

DOI10.1007/978-3-642-02017-9_31zbMath1241.68130OpenAlexW2148371453MaRDI QIDQ3630213

Saket Saurabh, Daniel Lokshtanov, Matthias Mnich

Publication date: 3 June 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02017-9_31

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

A Retrospective on (Meta) Kernelization ⋮ 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 ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ An Improved Kernel for Planar Connected Dominating Set ⋮ On parameterized independent feedback vertex set ⋮ Bidimensionality and Kernels ⋮ Kernelization: New Upper and Lower Bound Techniques

This page was built for publication: Linear Kernel for Planar Connected Dominating Set