An exact algorithm for connected red-blue dominating set

Faisal Abu Khzam, A.E. Mouawad, M Liedloff

Research output: Contribution to journalArticlepeer-review


In the Connected Red–Blue Dominating Set problem we are given a graph G whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset S of B such that each red vertex of G is adjacent to some vertex in S. The problem can be solved in O(2n|B| ) time by reduction to the Weighted Steiner Tree problem. Combining exhaustive enumeration when |B| is small with the Weighted Steiner Tree approach when |B| is large, solves the problem in O(1.4143n). In this paper we present a first non-trivial exact algorithm whose running time is in O(1.3645n). We use our algorithm to solve the Connected Dominating Set problem in O(1.8619n). This improves the current best known algorithm, which used sophisticated run-time analysis via the measure and conquer technique to solve the problem in O(1.8966n).
Original languageEnglish
Pages (from-to)252-262
Number of pages11
JournalJournal of Discrete Algorithms
Issue number3
Publication statusPublished - 2011
Externally publishedYes


Dive into the research topics of 'An exact algorithm for connected red-blue dominating set'. Together they form a unique fingerprint.

Cite this