Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Power Domination in Using Reference Search Trees
verfasst von : Daniel Raible, Henning Fernau
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 we have applied the next two rules exhaustively. 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 designed an algorithm solving this problem in time
$\mathcal{O}^*(1.7548^n)$
on general graphs. To achieve this we have used a new notion of search trees called reference search trees providing non-local pointers.