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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2017, 217, pp.536-547. 〈10.1016/j.dam.2016.09.045〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481785
Contributeur : Ignasi Sau <>
Soumis le : jeudi 2 mars 2017 - 21:49:03
Dernière modification le : vendredi 7 septembre 2018 - 14:04:02

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

138