Article ID Journal Published Year Pages File Type
4949761 Discrete Applied Mathematics 2017 12 Pages PDF
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 43k.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,