Power Domination on Graphs
Date Issued
2004
Date
2004
Author(s)
Chien, Yu-Yen
DOI
en-US
Abstract
Electric power companies monitor the state of their electric power system by placing phasor measurement units in the system. For economical considerations, companies have to place as few phasor measurement units as possible and still maintain the ability of monitoring the entire system. This problem can be theoretically represented as a variation of the well-known domination problem in graph theory as follows. A set S is a power dominating set of a graph G if every vertex and every edge of G can be monitored by 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 of G. In this thesis, we investigate the relation between power domination and domination, and use the NP-completeness of the domination problem to show that the power domination problem is NP-complete for chordal bipartite graphs and planar graphs with maximum degree 4. We also introduce the concept of partitioning a graph into induced subgraphs of power domination number 1 and give an upper bound of power domination number. In the last section, we give an alternative linear-time algorithm for the power domination problem on trees.
Subjects
支配
電力監測
電力支配
domination
electric power monitoring
power domination
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R91221005-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):d880bfb8f13484ef0f01573e67317126