A linear kernel for planar red–blue dominating set

Valentin Garnero 1 Ignasi Sau 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

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, September 7, 2018 - 2:04:02 PM

Links full text

Identifiers

Collections

Citation

Valentin Garnero, Ignasi Sau, 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⟩

Share

Metrics

Record views

186