# 臺灣博碩士論文加值系統

(34.204.198.73) 您好！臺灣時間：2024/07/21 15:34

:::

### 詳目顯示

:
 Twitter

DOI:10.6342/NTU202302534

• 被引用:0
• 點閱:28
• 評分:
• 下載:0
• 書目收藏:0
 圖 G 上的羅馬支配是我們為每個圖上的點分配值 0、1 或 2，並且滿足每個分配值為 0 的點需要至少一個分配值為 2 的點作為它的鄰居。羅馬支配的權重是指所有頂點賦值的總和。圖 G 如果滿足存在一組在同一個圓上的弧的集合 F，且每條在集合中的弧對應圖 G 的一個點，並且如果圖上的點 v 和點 u 有一條邊相連當且僅當它們對應的弧相交。我們稱這圖為圓環弧圖。羅馬支配問題是在所有可能的羅馬支配中找到一個權重最小的羅馬支配。在本論文中，我們希望找到一種算法來解決圓環弧圖上的羅馬支配問題。
 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.
 Verification Letter from the Oral Examination Committee iAcknowledgements ii摘要 iiiAbstract ivContents vList of Figures viList of Tables viiChapter 1 Introduction 11.1 Roman domination 11.2 Circular-arc graphs and interval graphs 3Chapter 2 Roman Domination on Circular-Arc Graphs 6Chapter 3 Algorithm and Time Complexity 113.1 Algorithm implementation 113.2 Time complexity 17Chapter 4 Conclusion 20References 23
 [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
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 基於深度學習的 X 光檢查流程醫療輔助系統 2 在置換生成圖中尋找最小的 k 距支配集 3 開發通用型標靶靈敏脂質體以檢測 O157:H7 型大腸桿菌 4 利用高通量蛋白質體微陣列發現泌尿道致病性大腸桿菌（UPEC）的潛在毒力因子 5 利用食源性細菌蛋白體微陣列晶片分析自體免疫葡萄膜炎的抗體組 6 開發水溶性雙羥甲基吡咯酞嗪複合物作為具有抗血管新生和DNA交聯雙重功能的抗癌藥物 7 放射治療對於非小細胞肺癌病患之預後影響以及放射性肺炎與劑量之分析 8 以角色為基礎的校園網路切割 9 利用受挫式全反射法及激發表面電漿波 Otto 組態對樟腦酰亞胺研究 10 藉由數據封包處理技術實現5G用戶平面功能 11 圓形圖上完全支配問題的近似演算法 12 電子斷層掃描顯微術重建高分子嵌段共聚物之三維結構及結構內結構 13 同調光繞射顯微術相位回復演算法之速度優化及於斷層掃描影像重建的應用 14 奈米粒子之原子級影像拍攝與重構 15 療癒風格插畫之創作研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室