Restricted power domination and fault-tolerant power domination on grids |
| |
Authors: | Kung-Jui Pai |
| |
Institution: | a Department of Industrial Engineering and Management, Mingchi University of Technology, Taipei County, Taiwan b Institute of Information Science and Management, National Taipei College of Business, Taipei, Taiwan c Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan |
| |
Abstract: | The power domination problem is to find a minimum placement of phase measurement units (PMUs) for observing the whole electric power system, which is closely related to the classical domination problem in graphs. For a graph G=(V,E), the power domination number of G is the minimum cardinality of a set S⊆V such that PMUs placed on every vertex of S results in all of V being observed. A vertex with a PMU observes itself and all its neighbors, and if an observed vertex with degree d>1 has only one unobserved neighbor, then the unobserved neighbor becomes observed. Although the power domination problem has been proved to be NP-complete even when restricted to some special classes of graphs, Dorfling and Henning in M. Dorfling, M.A. Henning, A note on power domination in grid graphs, Discrete Applied Mathematics 154 (2006) 1023-1027] showed that it is easy to determine the power domination number of an n×m grid. Their proof provides an algorithm for giving a minimum placement of PMUs. In this paper, we consider the situation in which PMUs may only be placed within a restricted subset of V. Then, we present algorithms to solve this restricted type of power domination on grids under the conditions that consecutive rows or columns form a forbidden zone. Moreover, we also deal with the fault-tolerant measurement placement in the designed scheme and provide approximation algorithms when the number of faulty PMUs does not exceed 3. |
| |
Keywords: | Grids Power domination Restricted power domination Fault-tolerant power domination |
本文献已被 ScienceDirect 等数据库收录! |
|