The power domination problem is an optimization problem that has emerged together with the development of the power networks. It is important to control the voltage and current in all the nodes and links in a power network. Measuring devices are expensive, which is why there is a tendency to place a minimum number of devices in a power network so that the network remains fully supervised. The k-power domination is a generalization of the power domination. The thesis represents the rules of the dissemination of the control in the network. A linear algorithm is provided for finding the optimal k-power dominating set on trees and followed by the implementation of the algorithm in Java. At the end NP-completeness for the power domination problem on bipartite graphs is proved.
|
