# A linear kernel for planar red–blue dominating set

1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In the Red-Blue Dominating Set problem, we are given a bipartite graph $G=(VB∪VR,E)$ and an integer $k$, and asked whether G has a subset $D⊆VB$ of at most $k$ "blue" vertices such that each "red" vertex from $VR$ is adjacent to a vertex in $D$. We provide the first explicit linear kernel for this problem on planar graphs, of size at most 46k.
Keywords :
Document type :
Journal articles
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481785
Contributor : Ignasi Sau <>
Submitted on : Thursday, March 2, 2017 - 9:49:03 PM
Last modification on : Friday, July 9, 2021 - 2:40:02 PM

### Citation

Valentin Garnero, Ignasi Sau Valls, Dimitrios M. Thilikos. A linear kernel for planar red–blue dominating set. Discrete Applied Mathematics, Elsevier, 2017, 217, pp.536-547. ⟨10.1016/j.dam.2016.09.045⟩. ⟨lirmm-01481785⟩

Record views