Logo image
Se connecter
A linear kernel for planar red-blue dominating set
Acte de colloque   Open Access

A linear kernel for planar red-blue dominating set

Valentin Garnero, Ignasi Sau et Dimitrios M. Thilikos
12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.117-120
CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization (Enschede, Netherlands, 21/05/2013–23/05/2013)
22/05/2013

Résumé

parameterized complexity planar graphs linear kernels domination
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.

Fichiers et liens (1)

url
Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Logo image