Abstract
Based on the power observation rules, the problem of monitoring a power utility network can be transformed into the graph-theoretic power domination problem, which is an extension of the well-known domination problem. A set (Formula presented.) is a power dominating set (PDS) of a graph (Formula presented.) if every vertex (Formula presented.) in (Formula presented.) can be observed under the following two observation rules: (1) (Formula presented.) is dominated by (Formula presented.), i.e., (Formula presented.) or (Formula presented.) has a neighbor in (Formula presented.); and (2) one of (Formula presented.)'s neighbors, say (Formula presented.), and all of (Formula presented.)'s neighbors, except (Formula presented.), can be observed. The power domination problem involves finding a PDS with the minimum cardinality in a graph. Similar to message passing protocols, a PDS can be considered as a dominating set with propagation that applies the second rule iteratively. This study investigates a generalized power domination problem, which limits the number of propagation iterations to a given positive integer; that is, the second rule is applied synchronously with a bounded time constraint. To solve the problem in block graphs, we propose a linear time algorithm that uses a labeling approach. In addition, based on the concept of time constraints, we provide the first nontrivial lower bound for the power domination problem. © 2014 Springer Science+Business Media New York.