 |
HAL-LIRMM - Open Archive |  |
Conference papers
A linear kernel for planar red-blue dominating set
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.
Cited literature [9 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00846771
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, July 19, 2013 - 7:53:14 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Monday, October 21, 2013 - 11:16:14 AM
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, July 19, 2013 - 7:53:14 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Monday, October 21, 2013 - 11:16:14 AM
File
RB_Dom_Set-CTW.pdf
Files produced by the author(s)