Skip to Main content Skip to Navigation
Journal articles

A linear kernel for planar red–blue dominating set

Valentin Garnero 1 Ignasi Sau Valls 1 Dimitrios M. Thilikos 2, 1
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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Ignasi Sau <>
Submitted on : Thursday, March 2, 2017 - 9:49:03 PM
Last modification on : Monday, May 4, 2020 - 9:42:03 AM

Links full text




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