A Linear Kernel for Planar Red-Blue Dominating Set
Valentin GarneroIgnasi SauDimitrios M. Thilikos
所有作者
Valentin GarneroIgnasi SauDimitrios M. Thilikos
文献摘要
In the Red-Blue Dominating Set problem, we are given a bipartite graph $G =
(V_B \cup V_R,E)andanintegerk,andaskedwhetherGhasasubsetD
\subseteq V_Bofatmostk"blue"verticessuchthateach"red"vertexfromV_RisadjacenttoavertexinD$. We provide the first explicit linear
kernel for this problem on planar graphs, of size at most 43k.