請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48915
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳健輝 | |
dc.contributor.author | Wei-Chieh Kao | en |
dc.contributor.author | 高偉傑 | zh_TW |
dc.date.accessioned | 2021-06-15T11:11:26Z | - |
dc.date.available | 2016-08-25 | |
dc.date.copyright | 2016-08-25 | |
dc.date.issued | 2016 | |
dc.date.submitted | 2016-08-22 | |
dc.identifier.citation | Bibliography
[1] Wayne Goddard,Michael A. Henning. Independent dominationin graphs: A survey and recent results. Discrete Mathematics Volume 313, 839–854, 2013. [2] E. Sampathkumar and H.B. Walikar. The connected domination number of a graph. J. Math. Phys. Sci. 13(6), 607–613, 1979. [3] Cockayne et al. Total domination in graphs. Networks 10, 1980. [4] J. Pfaff, R.C. Laskar, S.T. Hedetniemi. NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428, 1983. [5] J.M. Keil The complexity of domination problems in circle graphs. Discrete Appl. Math. 42 51-63, 1993. [6] R.C. Laskar, J. Pfaff, S.M. Hedetniemi, S.T. Hedetniemi. On the algorithmic complexity of total domination. SIAM J. Algebraic Discrete Methods 5 420–425, 1984. [7] R.C. Laskar, J. Pfaff. Domination and irredundance in split graphs. Technical Report 430, 1983. [8] M.S. Chang, S.C. Wu, G.J. Chang, H.G. Yeh. Domination in distance-hereditary graphs. Discrete Appl. Math. 116 103–113, 2002. [9] D. Kratsch, L. Stewart. Total domination and transformation. Inform. Process. Lett. 63 167-170, 1997. [10] A. Brandstぴadt, D. Kratsch. On domination problems on permutation and other graphs. Theoret. Comput. Sci. 54 181–198, 1987. [11] G.J. Chang. Labeling algorithms for domination problems in sunfree chordal graphs. Discrete Appl. Math. 22 21–34, 1988. [12] G.J. Chang. Total domination in block graphs. Oper. Res. Lett. 8 53–57, 1989. [13] G. Ramalingam, C.P. Rangan. Total domination in interval graphs revisited. Inform. Process. Lett. 27 17–21, 1988. [14] A. Rao, C. Pandu Rangan Optimal parallel algorithms on circulararc graphs. Inform. Process. Lett. 33 147–156, 1989. [15] M.S. Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs chordal graphs. SIAM J. Comput. 27 1671–1694, 1998. [16] C. Rhee, Y.D. Liang, S.K. Dhall and S. Lakshmivarahan. An O(n+m) algorithm for finding a minimum-weight dominating set in a permutation graph. SIAM J. Comput. 25 404-419, 1996. [17] K.S. NATARAJAN and Lee J. WHITE. OPTIMUM DOMINATION IN WEIGHTED TREES. Inform. Process. Lett. 7 261-265, 1978. [18] Chain-Chin Yen, R.C.T. Lee. The weighted perfect domination problem and its variants. Discrete Appl. Math. 66 147-160, 1996. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48915 | - |
dc.description.abstract | 本論文設計一演算法來解決權重仙人掌圖上的完全支
配點問題。給定一張由點與邊所組成的圖,支配集為圖 上的點所構成的一個點集合,而圖上每個不在支配集裡 的點皆至少與一個在支配集裡的點相鄰,稱此點集合為 支配集。對於一張圖上的完全支配點集,則是圖上的每 個點都至少會與一個在支配集裡的點相鄰。一張圖的完 全支配集並不唯一,如何找到一完全支配集且此點集合 的點數量為所有的完全支配點中最少的,就是完全支配 點問題。此外,若對於一仙人掌圖上的每一個點都賦予 一權重,在此權重仙人掌圖上的完全支配點問題就是在 一有權重的仙人掌圖上找到一完全支配集,此集合的點 權重加總為所有的完全支配點集合中最小的。本論文提 出了一演算法來解決這個問題,此演算法的時間複雜度 為O(m + n)。 | zh_TW |
dc.description.abstract | A dominating set of a graph G = (V ,E) is a subset S in V
if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is said to be a total dominating set if every vertex is adjacent to a vertex in S. The total domination problem is to find a minimum size of a total dominating set of a graph. In addition, suppose that every vertex v belongs to V is associated with a weight w(v). The weight total domination problem is to find a total dominating set S such that its total weight W(S) = Σ{w(v) : v is in S} is minimum. In this paper, we provide a dyanmic programming algorithm for the weight total domination problem on cactus graphs. The time complexity of this algorithm is O(m + n). | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T11:11:26Z (GMT). No. of bitstreams: 1 ntu-105-R03922117-1.pdf: 899279 bytes, checksum: 2a6341664bd0442f26af2a1151543b31 (MD5) Previous issue date: 2016 | en |
dc.description.tableofcontents | 口試委員會審定書iii
誌謝v Acknowledgements vii 摘要ix Abstract xi 1 Introduction 1 1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Block-cut-vertex structure . . . . . . . . . . . . . . . . 3 2 Finding minimum-weight total domination on cactus graph 7 2.1 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Find four minimum-weight dominating sets 13 3.1 Determine Si for i = 2 . . . . . . . . . . . . . . . . . . 14 3.1.1 Finding D(H,u1) . . . . . . . . . . . . . . . . 14 3.1.2 Finding T(H,u1) . . . . . . . . . . . . . . . . 15 3.1.3 Finding T'(H,u1) . . . . . . . . . . . . . . . . 16 3.1.4 Finding T bar(H,u1) . . . . . . . . . . . . . . . . 17 3.2 Determine Si for 2 <= i <= k . . . . . . . . . . . . . . . 17 3.2.1 Finding D(Hi-1,ui-1) . . . . . . . . . . . . . 18 3.2.2 Finding T(Hi-1,ui-1) . . . . . . . . . . . . . . 19 3.2.3 Finding T'(Hi-1,ui-1) . . . . . . . . . . . . . 20 3.2.4 Finding T bar(Hi-1,ui-1) . . . . . . . . . . . . . . 21 4 Example 23 5 Time Complexity 27 6 Future Research 29 Bibliography 31 | |
dc.language.iso | en | |
dc.title | 權重仙人掌圖上的完全支配點問題 | zh_TW |
dc.title | Total Domination in Weighted Cactus Graph | en |
dc.type | Thesis | |
dc.date.schoolyear | 104-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 周信宏,林清池,傅榮勝 | |
dc.subject.keyword | 圖論,完全支配點問題,仙人掌圖,權重圖,動態規劃, | zh_TW |
dc.subject.keyword | graph theory,total domination problem,cactus graph,weighted graph,dynamic programming, | en |
dc.relation.page | 32 | |
dc.identifier.doi | 10.6342/NTU201603532 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2016-08-23 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 878.2 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。