|
|||||
|
|
Power Domination in Circular-Arc Graphs |
|
| Authors: | Chung-Shou Liao D T Lee |
| Affiliation: | 1. Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, 300, Taiwan 2. Department of Computer Science and Engineering, National Chung Hsing University, Taichung, 402, Taiwan 3. Dept. of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 4. Institute of Information Science, Academia Sinica, Nankang, Taipei, 115, Taiwan |
| Abstract: | A set S?V is a power dominating set (PDS) of a graph G=(V,E) if every vertex and every edge in G can be observed based on the observation rules of power system monitoring. The power domination problem involves minimizing the cardinality of a PDS of a graph. We consider this combinatorial optimization problem and present a linear time algorithm for finding the minimum PDS of an interval graph if the interval ordering of the graph is provided. In addition, we show that the algorithm, which runs in Θ(nlogn) time, where n is the number of intervals, is asymptotically optimal if the interval ordering is not given. We also show that the results hold for the class of circular-arc graphs. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |