JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]


Journal of Information Science and Engineering, Vol. 29 No. 6, pp. 1249-1263


Power Domination in Honeycomb Meshes

KUO-HUA KAO1, JOU-MING CHANG2, YUE-LI WANG3,+, HUO-HONG XU4 AND JUSTIE SU-TZU JUAN1
1Department of Computer Science and Information Engineering 
National Chi Nan University 
Nantou, 545 Taiwan 
2Institute of Information and Decision Sciences 
National Taipei College of Business 
Taipei, 100 Taiwan 
3Department of Information Management 
National Taiwan University of Science and Technology 
Taipei, 106 Taiwan 
4Data Processing Unit 
Directorate General of Highway 
Ministry of Transportation and Communication 
Taipei, 100 Taiwan

    The power domination problem is to find a minimum placement of phase measurement units (PMUs) for observing the whole electric power system represented by a graph. The number of such a minimum placement of PMUs is called the power domination number of G and is denoted by gp(G). Finding gp(G) of an arbitrary graph is known to be NP-complete. In this paper, we deal with the power domination problem on honeycomb meshes. For a t-dimensional honeycomb mesh HMt, we show that gp(HMt) = é2t/3ù. In particular, we present an O(t)-time algorithm as the placement scheme.

Keywords: algorithms, power domination, phase measurement units, honeycomb meshes, spread domination

  Retrieve PDF document (JISE_201306_11.pdf)