請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88642
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳健輝 | zh_TW |
dc.contributor.advisor | Gen-Huey Chen | en |
dc.contributor.author | 廖俊崴 | zh_TW |
dc.contributor.author | Chun-Wei Liao | en |
dc.date.accessioned | 2023-08-15T17:11:21Z | - |
dc.date.available | 2023-11-09 | - |
dc.date.copyright | 2023-08-15 | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2023-08-02 | - |
dc.identifier.citation | [1] S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics, 23(1):11–24, 1989.
[2] H. Balakrishnan, A. Rajaraman, and C. P. Rangan. Connected domination and steiner set on asteroidal triple-free graphs. In Algorithms and Data Structures, pages 131–141, 1993. [3] M.S. Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM Journal on Computing, 27(6):1671–1694, 1998. [4] H.S. Chao, F.R. Hsu, and R.C.T. Lee. An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discrete Applied Mathematics, 102(3):159–173, 2000. [5] L. Chen, C. Lu, and Z. Zeng. A linear-time algorithm for paired-domination problem in strongly chordal graphs. Information Processing Letters, 110(1):20–23, 2009. [6] L. Chen, C. Lu, and Z. Zeng. Labelling algorithms for paired-domination problems in block and interval graphs. Journal of combinatorial optimization, 19(4):457–470, 2010. [7] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, and S.T. Hedetniemi. Roman domi-nation in graphs. Discrete Mathematics, 278(1):11–22, 2004. [8] Jr. Dreyer, P. A. Applications and variations of domination in graphs. PhD thesis, 2000. [9] A. D'Atri and M. Moscarini. Distance-hereditary graphs, steiner trees, and connected domination. SIAM Journal on Computing, 17(3):521–538, 1988. [10] D. Kratsch. Domination and total domination on asteroidal triple-free graphs. Dis-crete Applied Mathematics, 99(1):111–123, 2000. [11] D. Kratsch and L. Stewart. Domination on cocomparability graphs. SIAM Journal on Discrete Mathematics, 6(3):400–417, 1993. [12] E. Lappas, S. D. Nikolopoulos, and L. Palios. An O(n)-time algorithm for the paired domination problem on permutation graphs. European Journal of Combinatorics, 34(3):593–608, 2013. [13] R. Laskar and J. Pfaff. Domination and irredundance in split graphs. In Tech. Rept. 430. Clemson University Clemson, SC, 1983. [14] M. Liedloff, T. Kloks, J. Liu, and S.L. Peng. Efficient algorithms for Roman dom-ination on some classes of graphs. Discrete Applied Mathematics, 156:3400–3415, 2008. [15] C.C. Lin, K.C. Ku, and C.H. Hsu. Paired-domination problem on distance-hereditary graphs. Algorithmica, 82(10):2809–2840, 2020. [16] C.C. Lin and H.L. Tu. A linear-time algorithm for paired-domination on circular-arc graphs. Theoretical Computer Science, 591:99–105, 2015. [17] C.H. Liu and G.J. Chang. Roman domination on strongly chordal graphs. Journal of Combinatorial Optimization, 26(3):608–619, 2013. [18] R.M. McConnell. Linear-time recognition of circular-arc graphs. Algorithmica, 37:93–147, 2003. [19] J. Pfaff, R. Laskar, and S.T. Hedetniemi. NP-completeness of total and connected domination and irredundance for bipartite graphs. In Tech. Rept. 428. Clemson Uni-versity Clemson, SC, 1983. [20] H. Qiao, L. Kang, M. Cardei, and D.Z. Du. Paired-domination of trees. Journal of Global Optimization, 25:43–54, 2003. [21] I. Stewart. Defend the roman empire! Scientific American, 281(6):136–138, 1999. [22] V. Tripathi, T. Kloks, A. Pandey, K. Paul, and H.L. Wang. Complexity of paired domination in AT-free and planar graphs. Theoretical Computer Science, 930:53–62, 2022. [23] K. White, M. Farber, and W. Pulleyblank. Steiner trees, connected domination and strongly chordal graphs. Networks, 15(1):109–124, 198 | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88642 | - |
dc.description.abstract | 圖 G 上的羅馬支配是我們為每個圖上的點分配值 0、1 或 2,並且滿足每個分配值為 0 的點需要至少一個分配值為 2 的點作為它的鄰居。羅馬支配的權重是指所有頂點賦值的總和。圖 G 如果滿足存在一組在同一個圓上的弧的集合 F,且每條在集合中的弧對應圖 G 的一個點,並且如果圖上的點 v 和點 u 有一條邊相連當且僅當它們對應的弧相交。我們稱這圖為圓環弧圖。羅馬支配問題是在所有可能的羅馬支配中找到一個權重最小的羅馬支配。在本論文中,我們希望找到一種算法來解決圓環弧圖上的羅馬支配問題。 | zh_TW |
dc.description.abstract | Roman domination on a graph G is that we assign values 0, 1, or 2 to each vertex, subject to the condition that vertices whose assigned values are 0 need at least one vertex whose assigned value is 2 to be its neighbor. The weight of a Roman domination is the sum of all assigned values of the vertices. A graph G is a circular-arc graph if there exists a set F of arcs on a circle in which every arc corresponds to a vertex of G and if vertex v and vertex u have an edge if and only if their corresponding arcs are intersected. The Roman domination problem is finding a Roman domination whose weight is minimum among all possible Roman dominations. In this thesis, we want to find an algo-rithm to solve Roman domination problem on circular-arc graphs. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-15T17:11:21Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2023-08-15T17:11:21Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i
Acknowledgements ii 摘要 iii Abstract iv Contents v List of Figures vi List of Tables vii Chapter 1 Introduction 1 1.1 Roman domination 1 1.2 Circular-arc graphs and interval graphs 3 Chapter 2 Roman Domination on Circular-Arc Graphs 6 Chapter 3 Algorithm and Time Complexity 11 3.1 Algorithm implementation 11 3.2 Time complexity 17 Chapter 4 Conclusion 20 References 23 | - |
dc.language.iso | en | - |
dc.title | 圓環弧圖上的羅馬支配問題 | zh_TW |
dc.title | The Roman Domination Problem on Circular-Arc Graphs | en |
dc.type | Thesis | - |
dc.date.schoolyear | 111-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.coadvisor | 林清池 | zh_TW |
dc.contributor.coadvisor | Ching-Chi Lin | en |
dc.contributor.oralexamcommittee | 張貴雲;傅榮勝;薛文蔚 | zh_TW |
dc.contributor.oralexamcommittee | Guey-Yun Chang;Jung-Sheng Fu;Wen-Wey Hseush | en |
dc.subject.keyword | 羅馬支配,支配問題,圓環弧圖, | zh_TW |
dc.subject.keyword | Roman domination,Domination problems,circular-arc graph, | en |
dc.relation.page | 25 | - |
dc.identifier.doi | 10.6342/NTU202302534 | - |
dc.rights.note | 未授權 | - |
dc.date.accepted | 2023-08-07 | - |
dc.contributor.author-college | 電機資訊學院 | - |
dc.contributor.author-dept | 資訊工程學系 | - |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf 目前未授權公開取用 | 758.46 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。