A linear kernel for planar connected dominating set

D. Lokshtanov, M. Mnich, S. Saurabh

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

12 Citaten (Scopus)


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 to obtain linear kernels for other problems on planar graphs.
Originele taal-2Engels
Pagina's (van-tot)2536-2543
Aantal pagina's8
TijdschriftTheoretical Computer Science
Nummer van het tijdschrift23
StatusGepubliceerd - 2011

Vingerafdruk Duik in de onderzoeksthema's van 'A linear kernel for planar connected dominating set'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit