Skip to Main content Skip to Navigation
Conference papers

A linear kernel for planar red-blue dominating set

Valentin Garnero 1 Ignasi Sau Valls 1 Dimitrios M. Thilikos 1, 2
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 = (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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, July 19, 2013 - 7:53:14 PM
Last modification on : Friday, July 9, 2021 - 2:40:02 PM
Long-term archiving on: : Monday, October 21, 2013 - 11:16:14 AM


Files produced by the author(s)


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



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



Record views


Files downloads