A linear kernel for planar red–blue dominating set

Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)536-547
Number of pages12
JournalDiscrete Applied Mathematics
Volume217
DOIs
StatePublished - Jan 30 2017

Keywords

  • Linear kernels
  • Parameterized complexity
  • Planar graphs
  • Red–blue domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A linear kernel for planar red–blue dominating set'. Together they form a unique fingerprint.

Cite this