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.
Original language | English (US) |
---|---|
Pages (from-to) | 536-547 |
Number of pages | 12 |
Journal | Discrete Applied Mathematics |
Volume | 217 |
DOIs | |
State | Published - Jan 30 2017 |
Keywords
- Linear kernels
- Parameterized complexity
- Planar graphs
- Red–blue domination
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics