(18.204.227.34) 您好!臺灣時間:2021/05/19 07:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:莊晉瑋
研究生(外文):Chin-Wei Chuang
論文名稱:二步支配問題在區塊圖上之研究
論文名稱(外文):A Study of 2-Step Domination Problem on Block Graphs
指導教授:彭勝龍彭勝龍引用關係
指導教授(外文):Sheng-Lung Peng
口試委員:謝孫源楊慶隆
口試委員(外文):Sun-Yuan HsiehChing-Nung Yang
口試日期:2020-07-15
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:38
中文關鍵詞:支配問題二步支配問題跳躍支配問題區塊圖
外文關鍵詞:Domination Problem2-Step Domination ProblemHop Domination ProblemBlock Graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:34
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
我們說節點集合D⊆V 是圖G = (V,E) 的二步支配子集合,指的是在節點集合V中的每個點都與至少一個D 中的節點距離剛好等於2,我們則稱集合D 為圖G的二步支配子集合。支配問題的目標是在給定的一個圖G 中,找到最小的支配子集合D。支配問題本身就是一個相當經典的問題,在過去有許多人進行詳盡的研究。但支配距離為二或以上卻有很多可以研究的空間,而且在支配距離為二以上的名詞定義有一些不同,例如像是:跳躍支配、二步支配...等,在本篇論文中,我們就針對二步支配問題去進行研究,解決在區塊圖上的二步支配問題,利用區塊圖的樹狀結構,我們修正一個時間複雜度為線性的演算法來解決區塊圖上的跳躍支配問題。並對該演算法進行延伸來解決區塊圖上的二步支配問題。
For a graph G = (V,E), D⊆V is a dominating set of G if for every vertex v∈V ,there exists a neighbor vertex u∈D.The domination problem on G is to find a dominating set D of the minimum cardinality. The domination problem is well-studied. However, there are few research with dominating distance equal to 2 or more.Recently, some domination problems are proposed considering dominating distance equal to 2 or more, e.g., hop domination and 2-step domination.For a graph G, D⊆V is a 2-step (hop) dominating set if for every vertex v∈V (v∈V-D), there exists a vertex u∈D such that the distance between v and u is equal to 2.In this paper, we study the hop and 2-step domination problems on block graphs. We use a tree-like structure of a block graph to propose a linear algorithm to solve the hop and 2-step domination problems on block graphs.
i
第一章 Introduction 1
第二章 Definitions and Previous works 3
第三章 Preliminaries 7
第四章 Proposed Algorithms 13
第五章 Conclusion and Future Work 19
[1] Sambhu Charan Barman, Madhumangal Pal, and Sukumar Mondal. An optimal algorithm to find minimum k-hop dominating set of interval graphs. Discrete Mathematics, Algorithms and Applications, 11(02), 2019.
[2] Jr Sergio Canoy, Reynaldo Villarobe Mollejon, and John Gabriel E. Canoy. Hop dominating sets in graphs under binary operations. European Journal of Pure and Applied Mathematics, 12(4):14551463, 2019.
[3] Yair Caro and Michael Henning. Simultaneous domination in graphs. Graphs and Combinatorics, 30, 01 2013.
[4] Gerard J. Chang. Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Applied Mathematics, 22(1):21 34, 1988.
[5] Gerard J. Chang. Algorithmic Aspects of Domination in Graphs, pages 1811 1877. Springer US, Boston, MA, 1998.
[6] Gerard J. Chang, Jiaojiao Wu, and Xuding Zhu. Rainbow domination on trees. Discrete Applied Mathematics, 158(1):8 12, 2010.
[7] Gary Chartrand, Frank Harary, Moazzem Hossain, and Kelly Schultz. Exact 2-step domination in graphs. Mathematica Bohemica, 120:125134, 1995.
[8] Natarajan Chidambaram and S.K. Ayyaswamy. Hop domination in graphs ii. Analele Stiintice ale Universitatii Ovidius Constanta, Seria Matematica, 23:187199, 06 2015.
[9] E. Cockayne, S. Goodman, and S. Hedetniemi. A linear algorithm for the domination number of a tree. Information Processing Letters, 4(2):41 44, 1975.
[10] Rafael S Coelho, Phablo Moura, and YoshikoWakabayashi. The k-hop connected dominating set problem: Hardness and polyhedra. Electronic Notes in Discrete Mathematics, 50:5964, 12 2015.
[11] Rafael S. Coelho, Phablo F. S. Moura, and Yoshiko Wakabayashi. The k-hop connected dominating set problem: hardness and polyhedra. Electronic Notes in Discrete Mathematics, 50:5964, 2015.
[12] Rafael S. Coelho, Phablo F. S. Moura, and Yoshiko Wakabayashi. The k-hop connected dominating set problem: approximation and hardness. Journal of Combinatorial Optimization, 34(4):10601083, 2017.
[13] G. Dror, A. Lev, and Y. Roditty. A note: some results in step domination of trees. Discrete Mathematics, 289(1):137 144, 2004.
[14] Jochen Harant, Anja Pruchnewski, and Margit Voigt. On dominating sets and independent sets of graphs. Combinatorics, Probability and Computing, 8(6):547553, 1999.
[15] T.W. Haynes, S. Hedetniemi, and P. Slater. Domination in Graphs: Volume 2: Advanced Topics. Chapman & Hall/CRC Pure and Applied Mathematics. Taylor & Francis, 1998.
[16] Michael Henning and Nicolas Lichiardopol. Distance domination in graphs with given minimum and maximum degree. Journal of Combinatorial Optimization, 34, 10 2016.
[17] Michael A. Henning and Nader Jafari Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics, 33(4):913927, 2017.
[18] Patricia Hersh. On exact n-step domination. Discrete Mathematics, 205(1):235 239, 1999.
[19] M. F. Jalalvand and N. J. Rad. On the complexity of k-step and k-hop dominating sets in graphs. Mathematica Montisnigri, 40:3641, 2017.
[20] James K. Lan and Gerard Jennhwa Chang. On the mixed domination problem in graphs. Theoretical Computer Science, 476:84 93, 2013.
[21] You Lu and Jun-Ming Xu. The p-domination number of complete multipartite graphs. Discrete Mathematics, Algorithms and Applications, 06(04):1450063, 2014.
[22] Kelly Schultz. Step domination in graphs. Ars Comb., 55, 04 2000.
[23] Douglas Brent West. Introduction to graph theory. Prentice Hall, Upper Saddle River, N.J., 2nd edition, 2001.
[24] Ben Wieland and Anant Godbole. On the domination number of a random graph. Electron J Combin, 8, 12 2001.
[25] Yancai Zhao, Zuhua Liao, and Lianying Miao. On the algorithmic complexity of edge total domination. Theoretical Computer Science, 557:28 33, 2014.
[26] Yancai Zhao, Lianying Miao, and Zuhua Liao. A linear-time algorithm for 2-step domination in block graphs. Journal of Mathematical Research with Applications, Vol. 35:285290, 2015.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文