Linear kernel for planar connected dominating set

D. Lokshtanov, M. Mnich, S. Saurabh

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationTheory and Applications of Models of Computation (6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings)
EditorsJ. Chen, S.B. Cooper
Place of PublicationBerlin
PublisherSpringer
Pages281-290
ISBN (Print)978-3-642-02016-2
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
Volume5532
ISSN (Print)0302-9743

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

Cite this