An Exact Exponential Time Algorithm for Power Dominating Set

Autor: Daniel Binkele-Raible, Henning Fernau
Rok vydání: 2011
Předmět:
Zdroj: Algorithmica. 63:323-346
ISSN: 1432-0541
0178-4617
Popis: The Power Dominating Set problem is an extension of the well-known domination problem on graphs in a way that we enrich it by a second propagation rule: given a graph G(V,E), a set P⊆V is a power dominating set if every vertex is observed after the exhaustive application of the following two rules. First, a vertex is observed if v∈P or it has a neighbor in P. Secondly, if an observed vertex has exactly one unobserved neighbor u, then also u will be observed, as well. We show that Power Dominating Set remains $\mathcal{NP}$ -hard on cubic graphs. We design an algorithm solving this problem in time $\mathcal{O}^{*}(1.7548^{n})$ on general graphs, using polynomial space only. To achieve this, we introduce so-called reference search trees that can be seen as a compact representation of usual search trees, providing non-local pointers in order to indicate pruned subtrees.
Databáze: OpenAIRE
Externí odkaz: