A linear kernel for a planar connected dominating set

Daniel Lokshtanov; Matthias Mnich; Saket Saurabh

doi:10.1016/j.tcs.2010.10.045

A linear kernel for a planar connected dominating set

Daniel Lokshtanov, Matthias Mnich, Saket Saurabh^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

We provide polynomial time data reduction rules for connected dominating set on planar graphs and analyze these to obtain a linear kernel for the planar connected dominating set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.

Original language	English
Pages (from-to)	2536-2543
Journal	Theoretical Computer Science
Volume	412
Issue number	23
DOIs	https://doi.org/10.1016/j.tcs.2010.10.045
Publication status	Published - 2011
Externally published	Yes

Access to Document

10.1016/j.tcs.2010.10.045Licence: Free access - publisher

Cite this

@article{6eb5e23e41d2427c82791dd4b7e32e0b,

title = "A linear kernel for a planar connected dominating set",

abstract = "We provide polynomial time data reduction rules for connected dominating set on planar graphs and analyze these to obtain a linear kernel for the planar connected dominating set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.",

author = "Daniel Lokshtanov and Matthias Mnich and Saket Saurabh",

year = "2011",

doi = "10.1016/j.tcs.2010.10.045",

language = "English",

volume = "412",

pages = "2536--2543",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier Science",

number = "23",

}

TY - JOUR

T1 - A linear kernel for a planar connected dominating set

AU - Lokshtanov, Daniel

AU - Mnich, Matthias

AU - Saurabh, Saket

PY - 2011

Y1 - 2011

N2 - We provide polynomial time data reduction rules for connected dominating set on planar graphs and analyze these to obtain a linear kernel for the planar connected dominating set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.

AB - We provide polynomial time data reduction rules for connected dominating set on planar graphs and analyze these to obtain a linear kernel for the planar connected dominating set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.

U2 - 10.1016/j.tcs.2010.10.045

DO - 10.1016/j.tcs.2010.10.045

M3 - Article

SN - 0304-3975

VL - 412

SP - 2536

EP - 2543

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 23

ER -