Lokshtanov, Daniel ; Mnich, Matthias ; Saurabh, Saket (2011) A Linear Kernel for Planar Connected Dominating Set Theoretical Computer Science, 412 (23). pp. 2536-2543. ISSN 0304-3975
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.tcs.2010.10.045
Related URL: http://dx.doi.org/10.1016/j.tcs.2010.10.045
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123468 |
| Deposited On: | 20 Sep 2021 10:15 |
| Last Modified: | 20 Sep 2021 10:15 |
Repository Staff Only: item control page
