Abstract
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 language | English |
---|---|
Pages (from-to) | 252-262 |
Number of pages | 11 |
Journal | Journal of Discrete Algorithms |
Volume | 9 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2011 |
Externally published | Yes |