Linear kernel for planar connected dominating set

D. Lokshtanov; M. Mnich; S. Saurabh

doi:10.1007/978-3-642-02017-9_31

Linear kernel for planar connected dominating set

D. Lokshtanov, M. Mnich, S. Saurabh

Combinatorial Optimization - EIDMA

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

17 Citations (Scopus)

Abstract

We provide polynomial time data reduction rules for Connected Dominating Set in 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 to obtain linear kernels for other problems on planar graphs.

Original language	English
Title of host publication	Theory and Applications of Models of Computation (6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings)
Editors	J. Chen, S.B. Cooper
Place of Publication	Berlin
Publisher	Springer
Pages	281-290
ISBN (Print)	978-3-642-02016-2
DOIs	https://doi.org/10.1007/978-3-642-02017-9_31
Publication status	Published - 2009

Publication series

Name	Lecture Notes in Computer Science
Volume	5532
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-02017-9_31

Fingerprint Dive into the research topics of 'Linear kernel for planar connected dominating set'. Together they form a unique fingerprint.

Cite this

Lokshtanov, D., Mnich, M., & Saurabh, S. (2009). Linear kernel for planar connected dominating set. In J. Chen, & S. B. Cooper (Eds.), Theory and Applications of Models of Computation (6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings) (pp. 281-290). (Lecture Notes in Computer Science; Vol. 5532). Springer. https://doi.org/10.1007/978-3-642-02017-9_31

@inproceedings{23ad90c3436a42a0aa1029ea88e660b2,

title = "Linear kernel for planar connected dominating set",

abstract = "We provide polynomial time data reduction rules for Connected Dominating Set in 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 to obtain linear kernels for other problems on planar graphs.",

author = "D. Lokshtanov and M. Mnich and S. Saurabh",

year = "2009",

doi = "10.1007/978-3-642-02017-9_31",

language = "English",

isbn = "978-3-642-02016-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "281--290",

editor = "J. Chen and S.B. Cooper",

booktitle = "Theory and Applications of Models of Computation (6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings)",

address = "Germany",

}

Lokshtanov, D, Mnich, M & Saurabh, S 2009, Linear kernel for planar connected dominating set. in J Chen & SB Cooper (eds), Theory and Applications of Models of Computation (6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings). Lecture Notes in Computer Science, vol. 5532, Springer, Berlin, pp. 281-290. https://doi.org/10.1007/978-3-642-02017-9_31

Linear kernel for planar connected dominating set. / Lokshtanov, D.; Mnich, M.; Saurabh, S.

Theory and Applications of Models of Computation (6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings). ed. / J. Chen; S.B. Cooper. Berlin : Springer, 2009. p. 281-290 (Lecture Notes in Computer Science; Vol. 5532).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Linear kernel for planar connected dominating set

AU - Lokshtanov, D.

AU - Mnich, M.

AU - Saurabh, S.

PY - 2009

Y1 - 2009

N2 - We provide polynomial time data reduction rules for Connected Dominating Set in 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 to obtain linear kernels for other problems on planar graphs.

AB - We provide polynomial time data reduction rules for Connected Dominating Set in 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 to obtain linear kernels for other problems on planar graphs.

U2 - 10.1007/978-3-642-02017-9_31

DO - 10.1007/978-3-642-02017-9_31

M3 - Conference contribution

SN - 978-3-642-02016-2

T3 - Lecture Notes in Computer Science

SP - 281

EP - 290

BT - Theory and Applications of Models of Computation (6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings)

A2 - Chen, J.

A2 - Cooper, S.B.

PB - Springer

CY - Berlin

ER -