請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57506完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
| dc.contributor.author | Cheng-Yu Hsieh | en |
| dc.contributor.author | 謝政佑 | zh_TW |
| dc.date.accessioned | 2021-06-16T06:49:04Z | - |
| dc.date.available | 2015-08-14 | |
| dc.date.copyright | 2014-08-14 | |
| dc.date.issued | 2014 | |
| dc.date.submitted | 2014-07-24 | |
| dc.identifier.citation | [1] H.-L. T. C.-C. Lin. Linear-time algorithms for the paired- domination problem in interval graphs and circular-arc graphs. Theoretical Computer Science, 2014.
[2] G. J. Chang. Total domination in block graphs. Operations Re- search Letters, 8:53–57, 1989. [3] G. J. Chang and S.-F. Hwang. The edge domination problem. Dis- cussiones Mathematicae Graph Theory, 15(1):51–57, 1995. [4] C. Y. T. Chih-Shan Liu, Sheng-Lung Peng. Weak roman domina- tion on block graphs, 27th workshop on combinatorial mathematics and computation theory. pages 86–89, 2010. [5] C. Y. T. Chin Lung Lu. Weighted efficient domination problem on some perfect graphs. Discrete Applied Mathematics, 117:163–182, 2002. [6] M.-S. C. Chuan-Min Lee. The weighted perfect domination prob- lem and its variants. Discrete Applied Mathematics, 66:147–160, 1996. [7] M.-S. C. Chuan-Min Lee. Variations of y-dominating functions on graphs. Discrete Mathematics, 308:4185–4204, 2008. [8] S. T. H. E. J. Cockayne, R. M. Dawes. Total domination in graphs. Networks, 10:211–219, 1998. [9] G. L. N. Gerard J Chang. R-domination on block graphs. Opera- tions Research Letters, 1:218–218, 1982. [10] E. S. M. Z. Guangjun Xu, Liying Kang. Power domination in block graphs. Theoretical Computer Science, 359:299–305, 2006. [11] M. A. Henning. A survey of selected recent results on total domi- nation in graphs. Discrete Applied Mathematics, 309:32–63, 2009. [12] M. C. D.-Z. D. Hong Qiao, Liying Kang. Paired-domination of trees. Journal of Global Optimization, 25:43–54, 2003. [13] G. J. C. James K. Lan. On the algorithmic complexity of k-tuple total domination. submitted to Elsevier, 2013. [14] Z. Z. Lei Chen, Changhong Lu. Hardness results and approxima- tion algorithm for (weighted) paired-domination in graphs. Theo- retical Computer Science, 410:47–49, 2009. [15] Z. Z. Lei Chen, Changhong Lu. A linear-time algorithm for paired- domination problem in strongly chordal graphs. Information Pro- cessing Letters, 110:20–23, 2009. [16] Z. Z. Lei Chen, Changhong Lu. Labelling algorithms for paired- domination problems in block and interval graphs. Journal of Com- binatorial Optimization, 19:457–470, 2010. [17] Z. Z. Lei Chen, Changhong Lu. Vertices in all minimum paired- dominating sets of block graphs. Journal of Combinatorial Opti- mization, 24:179–191, 2012. [18] T. C. Liying Kang, Moo Young Sohnb. Paired-domination in in- flated graphs. Theoretical Computer Science, 320:485–494, 2004. [19] E. L. S. D. N. L. Palios. An o(n)-time algorithm for the paired- domination problem on permutation graphs. European Journal of Combinatorics, 34:593–608, 2013. [20] S. H. S. Pinar Heggernes. Computer Science – Theory and Appli- cations. Springer Berlin Heidelberg, 2012. [21] C. N. T.C.E. Cheng, L.Y. Kang. Paired domination on interval and circular-arc graphs. Discrete Applied Mathematics, 155:2077– 2086, 2007. [22] E. S. T.C.E. Cheng, L.Y. Kang. A polynomial-time algorithm for the paired-domination problem on permutation graphs. Discrete Applied Mathematics, 157:262–271, 2009. [23] P. S. Teresa W. Haynes, Stephen Hedetniemi. Domination in Graphs: Advanced Topics. Marcel Dekker, 1998. [24] P. S. Teresa W. Haynes, Stephen Hedetniemi. Fundamentals of Domination in Graphs. CRC Press, 1998. [25] P. S. Teresa W. Haynes, Stephen Hedetniemi. Paired-domination in graphs. Networks, 32:199–206, 1998. [26] Z. L. R. G. Yancai Zhao, Erfang Shan. A labeling algorithm for distance domination on block graphs. Operations Research Letters, 8:53–57, 1989. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57506 | - |
| dc.description.abstract | 本論文提出一演算法來解決權重區塊圖上的成對支配 點問題。試想一由點與線構成的圖,支配集是圖上的點 構成的點集合,而圖上每個不在支配集裡的點都會至少 與一在支配集裡的點相鄰,如此就構成了支配集。而對 於一圖上的成對支配點集,就是既滿足支配集的定義又 滿足支配集裡點形成的誘導子圖上,點兩兩成對。在一 圖上無數成對支配集中,如何找到一成對支配集且此集 合點的數量為無數成對支配點中最少的,就是成對支配 點問題。此外,對於一區塊圖上的每一個點,我們都賦 予它一權重,如此在權重區塊圖上的成對支配點問題就 是在一點有權重的區塊圖上,找到一點的數量為最小且 點權重加總也為最小的成對支配點集合。在本論文中, 提出了 O(m + n) 時間複雜度的眼算法來解決這個問題。 | zh_TW |
| dc.description.abstract | AdominatingsetofagraphG=(V,E)isasubsetS ⊆V if every vertex not in S is adjacent to a vertex in S. A domi- nating set S of a graph G is called a paired dominating set if the induced subgraph G[S] contains a perfect matching. The paired domination problem is to find a minimum size of a paired dominating set of a graph. Suppose moreover that ev- ery vertex v ∈ V associate with a weight w(v). The weight paired domination problem is to find a paired dominating set S such that its total weight W(S) = ∑{w(v) : v ∈ S} is min- imum. In this paper, we provide an dyanmic programming algorithm with O(m + n)-time for the weight paired domina- tion problem on block graphs. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T06:49:04Z (GMT). No. of bitstreams: 1 ntu-103-R01922114-1.pdf: 1273436 bytes, checksum: 9bb9eb4a498a0b6dc750575d1f684f0c (MD5) Previous issue date: 2014 | en |
| dc.description.tableofcontents | 口試委員會審定書 ..........................................................................iii
誌謝 ..............................................................................................v 摘要 .............................................................................................vii Abstract .......................................................................................ix 1 Introduction ..............................................................................1 1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . ........................4 1.2 Block-cut-vertex structure . . . . . . . . . . . . . ......................5 2 Finding minimum-weight paired domination on block graph ....11 2.1 Basicidea........................................................................... 11 2.2 Algorithm......................................................................... 12 3 Time complexity 17 3.1 FindingD(H,u1)................................................................. 19 3.2 FindingP(H,u1).................................................................. 21 3.3 FindingP′(H,u1) ................................................................ 22 3.4 FindingP ̄(H,u1).................................................................. 29 4 Conclusion.................................................................................31 Bibliography..................................................................................33 | |
| dc.language.iso | zh-TW | |
| dc.subject | 動態規劃 | zh_TW |
| dc.subject | 成對支配點問題 | zh_TW |
| dc.subject | 區塊圖 | zh_TW |
| dc.subject | paired domination problem | en |
| dc.subject | block graph | en |
| dc.subject | dynamic programming | en |
| dc.title | 權重區塊圖上的成對支配點問題 | zh_TW |
| dc.title | Paired Domination on Block Graph | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 102-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 林清池(Ching-Chi Lin) | |
| dc.contributor.oralexamcommittee | 胡家正(Chia-Cheng Hu),周信宏(Hsin-Hung,Chou) | |
| dc.subject.keyword | 成對支配點問題,區塊圖,動態規劃, | zh_TW |
| dc.subject.keyword | paired domination problem,block graph,dynamic programming, | en |
| dc.relation.page | 35 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2014-07-24 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-103-1.pdf 未授權公開取用 | 1.24 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。