Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949761 | Discrete Applied Mathematics | 2017 | 12 Pages |
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
Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos,