跳到主要內容

臺灣博碩士論文加值系統

(34.204.198.73) 您好!臺灣時間:2024/07/21 15:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:廖俊崴
研究生(外文):Chun-Wei Liao
論文名稱:圓環弧圖上的羅馬支配問題
論文名稱(外文):The Roman Domination Problem on Circular-Arc Graphs
指導教授:陳健輝陳健輝引用關係林清池林清池引用關係
指導教授(外文):Gen-Huey ChenChing-Chi Lin
口試委員:張貴雲傅榮勝薛文蔚
口試委員(外文):Guey-Yun ChangJung-Sheng FuWen-Wey Hseush
口試日期:2023-07-27
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2023
畢業學年度:111
論文頁數:25
中文關鍵詞:羅馬支配支配問題圓環弧圖
外文關鍵詞:Roman dominationDomination problemscircular-arc graph
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 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
[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
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top