請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37408
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張鎮華(Gerard Jennhwa Chang) | |
dc.contributor.author | Chien-Cheng Chuang | en |
dc.contributor.author | 莊建成 | zh_TW |
dc.date.accessioned | 2021-06-13T15:27:09Z | - |
dc.date.available | 2009-06-23 | |
dc.date.copyright | 2009-06-23 | |
dc.date.issued | 2008 | |
dc.date.submitted | 2008-07-17 | |
dc.identifier.citation | [1] A. Aazami and M. D. Stilp, Approximation algorithms and hardness for domination with propagation, LNCS, 4627 (2007) pp. 1-15.
[2] 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(2) (1993) pp. 707-715. [3] D. J. Brueni and L. S. Heath, The PMU placement problem, SIAM J. Discrete Math., 19(3) (2005) pp. 744-761. [4] G. J. Chang, Algorithmic aspects of domination in graphs, in: Handbook of Combinatorial Optimization Vol. 3 (D.-Z. Du and P. M. Pardalos eds.), Kluwer Academic Publishers, Boston, (1998) pp. 339-405. [5] Y.-Y. Chien, Power Domination on Graphs, Master Thesis, National Taiwan University, Taipei, Taiwan (2004). [6] M. Dorfling and M. A. Henning, A note on power domination in grid graphs, Discrete Applied Math., 154 (2006) pp. 1023-1027. [7] J. Guo, R. Niedermeier, and D. Raible, Improved algorithms and complexity results for power domination in graphs, accepted and published online by Algorithmica (2007). [8] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and M. A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Math., 15(4) (2002) pp. 519-529. [9] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, (1998). [10] J. Kneis, D. M‥olle, S. Richter, and P. Rossmanith, Parameterized power domination complexity, Information Processing Letters, 98 (2006) pp. 145-149. [11] C.-S. Liao, Algorithmic Aspects of Domination and Applications on Graphs, Research Proposal of Ph.D. Dissertation, National Taiwan University, Taipei, Taiwan (2008). [12] C.-S. Liao and D.-T. Lee, Power domination problems in graphs, LNCS, 3595 (2005) pp. 818-828. [13] D. B. West, Introdution to Graph Theory, Second Edition, Prentce Hall, New Jersey, (2001). [14] G. Xu, L. Kang, E. Shan, and M. Zhao, Power domination in block graphs, Theoretical Computer Science, 359 (2006) pp. 299-305. [15] M. S. Yu, and C. H. Yang, A linear time algorithm for the maximum matching problem on cographs, BIT Numerical Math., 33(3) (1993) pp. 420-432. [16] M. Zhao, L. Kang, and G. J. Chang, Power domination in graphs, Discrete Math., 306 (2006) pp. 1812-1816. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37408 | - |
dc.description.abstract | 電力公司為了監控他們的電力系統,必須在系統中選定的位置上放置位相測量單位以監控電力系統的狀態。由於它的成本較高,因此電力公司必須儘可能地放置最少的位相測量單位,並使得整個系統仍然能夠被監控到以節省成本。這個問題可以視為圖論中支配問題的一種變化形,我們稱之為電力支配問題。
我們以圖論的方式來看電力支配問題:對於一個給定的圖G,如果一個頂點集的子集S,依循下列電力支配的方法可以監測到圖G的所有頂點和邊,則我們稱S是一個圖G的電力支配集:(1)S和S的鄰居可以被監測到;(2)如果有一個已經被S監測到的頂點,只剩下一個鄰居尚未被監測到,則此未被監測到的頂點可以自動地被監測到。而我們的目的是希望找到頂點數最少的電力支配集,這個最小的數目稱為圖G的電力支配數。 對於電力支配問題的研究方面,陸續已經有不少的結果被發表。而在這篇文章中,我們一開始先証明在兩個圈的卡氏積上電力支配問題的結果;接下來以演算法的觀點,分別在P_4-免除圖和樹狀圖上各給出一個演算法來找出其最小的電力支配集。 | zh_TW |
dc.description.abstract | Electric power companies monitor the state of their electric power system by placing phase measurement units (PMUs) at selected locations in the system. They want to place as few measurement devices as possible such that these devices still monitor the whole system. This problem can be considered as a variation of the domination problem in graph theory, which we call the power domination problem.
Power domination problem is defined as follows: given a graph G, a subset S is called a power dominating set if every vertex of G can be observed by S by repeatedly applying the following rules: (i) vertices in S and their neighbors are observed; (ii) if at some stage an observed vertex has exactly one unobserved neighbor, then this neighbor is observed. The purpose of the problem is to find a minimum power dominating set S of G. The minimum cardinality of a power dominating set of G is called the power domination number $gamma_p(G)$. In this thesis, we first determine the power domination numbers of the Cartesian product of two cycles. We then investigate the properties of co-graphs and give an algorithm for the power domination problem on co-graphs. Finally, we present a labeling algorithm for the power domination problem on trees. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T15:27:09Z (GMT). No. of bitstreams: 1 ntu-97-R95221001-1.pdf: 299156 bytes, checksum: 4daf73d525306eef9aa844c0e67fc72e (MD5) Previous issue date: 2008 | en |
dc.description.tableofcontents | Acknowledgements i
Abstract (in Chinese) ii Abstract (in English) iii Contents iv Figures iv Tables iv 1 Introduction 1 2 Cartesian Product of Cycles 5 3 Cographs 10 4 Trees 16 References 19 | |
dc.language.iso | zh-TW | |
dc.title | 圖上電力支配問題的研究 | zh_TW |
dc.title | Study on Power Domination of Graphs | en |
dc.type | Thesis | |
dc.date.schoolyear | 96-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 朱緒鼎,葉鴻國 | |
dc.subject.keyword | 支配,電力支配, | zh_TW |
dc.subject.keyword | domination,power domination,tree,cograph, | en |
dc.relation.page | 20 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2008-07-18 | |
dc.contributor.author-college | 理學院 | zh_TW |
dc.contributor.author-dept | 數學研究所 | zh_TW |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 292.14 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。