二分排列圖限制在最大分支度為4的電力支配問題

Power Domination on Bipartite Permutation Graphs of Maximum Degree 4

許志榮(Chih-Jung Hsu)

指導教授 ： 王有禮

國立暨南國際大學/科技學院/資訊工程學系/碩士(2008年)

https://doi.org/10.6837/NCNU.2008.00056

摘要

電力公司在其電力系統當中放置位相量測單元(phase measurement units 簡稱PMUs)以監測系統的狀態。為了節省成本，電力公司必須儘可能以少量的位相量測單元來監測整個系統。這個問題可以視為圖論中支配問題的推廣。對圖Ｇ來說，若點集合的子集Ｓ能夠根據電力系統監測的規則監測到Ｇ所有的點和邊，我們稱Ｓ為Ｇ的電力支配集(power domination set 簡稱PDS)，而Ｇ的最小電力支配集的元素個數稱為Ｇ的電力支配數 (G)。電力支配問題已經有人證明在二分圖(bipartite graphs)和弦圖(chordal graphs)中是NP-complete。在本論文中，我們提出一個O(E2)演算法，可以在二分排列圖(bipartite permutation graphs)限制在最大分支度為4，解決電力支配問題。

關鍵字

演算法 ； 電力支配數集合 ； 二分排列圖 ； 電子電力系統

並列摘要

Electric power companies monitor the state of their electric power system by placing phase measurement units (PMUs) in the system. For economical considerations, companies have to place a few phase 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. 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 (G) of G. This problem was proved NP-complete even when restricted to bipartite graphs and chordal graphs. In this thesis, we present an O(E2) algorithm for solving the power domination problem in bipartite permutation graphs of maximum degree 4.

並列關鍵字

Algorithm ； Power domination set ； Bipartite permutation graphs ； Electric power system

參考文獻

[1] D. Atkins, T.W. Haynes, and M.A. Henning, Placing monitoring devices in electric power networks modelled by block graphs, Ars Combinatoria 79 (2006) 129-143.

[2] A.V. Aho, J.E. Hopcropt, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.

[3] A. Brandstädt, V.V. Lozin, On the linear structure and cliquewidth of bipartite permutation graphs, Ars Combinatoria 67 (2003) 273–281.

[4] T.L. Baldwin, L. Mili, M.B. Boisen, Jr., and R. Adapa, Power system observability with minimal phasor measurement placement, IEEE Trans. Power Systems 8 (1993) 707-715.

[5] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Elsevier, North-Holland, Amsterdam, 1976.