"Domination in Graphs Applied to Electric Power Networks" by Teresa W. Haynes, Sandra M. Hedetniemi et al.
 

Domination in Graphs Applied to Electric Power Networks

Document Type

Article

Publication Date

7-1-2002

Description

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graphs. We consider the graph theoretical representation of this problem as a variation of the dominating set problem and define a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph G is the power domination number γP(G). We show that the power dominating set (PDS) problem is NP-complete even when restricted to bipartite graphs or chordal graphs. On the other hand, we give a linear algorithm to solve the PDS for trees. In addition, we investigate theoretical properties of γP(T) in trees T.

Plum Print visual indicator of research metrics
PlumX Metrics
  • Citations
    • Citation Indexes: 272
  • Usage
    • Abstract Views: 37
  • Captures
    • Readers: 48
see details

Share

COinS