A linear kernel for planar red–blue dominating set - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discrete Applied Mathematics Année : 2017

A linear kernel for planar red–blue dominating set

Résumé

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.

Dates et versions

lirmm-01481785 , version 1 (02-03-2017)

Identifiants

Citer

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

Altmetric

Partager

More