A linear kernel for planar red-blue dominating set - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

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 = (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.
Fichier principal
Vignette du fichier
RB_Dom_Set-CTW.pdf (99.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00846771 , version 1 (19-07-2013)

Identifiants

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

Citer

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. pp.117-120. ⟨lirmm-00846771⟩
159 Consultations
433 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More