A linear kernel for planar red-blue dominating set

Valentin Garnero 1 Ignasi Sau 1 Dimitrios M. Thilikos 1, 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 Department of Mathematics [Athens]
Abstract : In the Red-Blue Dominating Set problem, we are given a bipartite graph $G = (V_B \cup V_R,E)$ and an integer $k$, and asked whether $G$ has a subset $D \subseteq V_B$ of at most $k$'blue' vertices such that each 'red' vertex from $V_R$ is adjacent to a vertex in $D$. We provide the first explicit linear kernel for this problem on planar graphs.
Keywords : domination linear kernels planar graphs parameterized complexity
Type de document :
Communication dans un congrès
CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2013, Enschede, Netherlands. 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.117-120, 2013, 〈http://wwwhome.math.utwente.nl/~ctw/index.php?page=home〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00846771
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 19 juillet 2013 - 19:53:14
Dernière modification le : jeudi 19 juillet 2018 - 18:40:02
Document(s) archivé(s) le : lundi 21 octobre 2013 - 11:16:14

Fichier

RB_Dom_Set-CTW.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00846771, version 1
  • ARXIV : 1408.6388

Collections

LIRMM | ALGCO | MIPS | TDS-MACS | UNIV-MONTPELLIER

Citation

Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos. A linear kernel for planar red-blue dominating set. CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2013, Enschede, Netherlands. 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.117-120, 2013, 〈http://wwwhome.math.utwente.nl/~ctw/index.php?page=home〉. 〈lirmm-00846771〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

366

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD