pith. sign in

arxiv: 1408.6388 · v3 · pith:YEMPYH5Unew · submitted 2014-08-27 · 💻 cs.DS

A Linear Kernel for Planar Red-Blue Dominating Set

classification 💻 cs.DS
keywords dominatingkernellinearplanarproblemred-bluevertexadjacent
0
0 comments X
read the original 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, of size at most $43k$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.