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

(44.211.237.117) 您好！臺灣時間：2024/08/11 11:03

:::

### 詳目顯示

:

• 被引用:0
• 點閱:166
• 評分:
• 下載:11
• 書目收藏:0
 近年來有一個相當熱門的支配圖(domination problem)變形問題，叫做羅馬支配問題(Roman domination problem)。是說在一個圖(graph) G＝（V, E）上，一個羅馬支配函數(roman dominating function)是一個函數(function) f : V �� {0, 1, 2}，會使得V中任意一個點 u ，其f(u) = 0， 必會存在一個與u相鄰之點 v 其f(v) = 2，u與v 屬於V。一個羅馬支配函數f的值就是把V中所有的點所對應的值(weight)給全部加總起來。圖G的一個羅馬支配數值(roman domination number)就是在G之中其所有可能的羅馬支配函數其值的最小總和。當我們被給定一個排列圖(permutation graph)的時候，則此篇文章能提供一個多項式時間(polynomial time) O(n5)的演算法。利用動態規劃(dynamic programming)的方法來找出排列示圖(permutation diagram)上其所有可能的有序交叉對(order cross pair)，並針對每一組有序交叉對，找出當時對他而言最佳的一組解，進而最後組合成整張圖最佳解的羅馬支配函數。
 A roman domination problem is quite a hot variant domination problem in recent years. In one graph G = (V, E), a roman domination function is a function f : V �� {0, 1, 2}, that each one vertex u with f(u) = 0 is adjacent to at least one vertex v with f(v) = 2, among them u and v belongs to V. The weight of a roman domination function f is the sum of the weight of V. A roman domination number of a graphs G is the smallest weight of the possible roman domination function f. When give one permutation graph, we can provide a polynomial algorithm (O(n5))to find out the roman domination number by using the method of dynamic programming. It checks all the possible order cross pairs. With regard to each order cross pair, we find out the best solution for it at that time. Finally we combine the solution to solve roman dominating function.
 摘要 i目錄頁 ii表格列 iii圖列 ivCHAPTER 1 (INTRODUCTION) 1CHAPTER 2 (PRELIMINARIES) 5CHAPTER 3 (ALGORITHM) 9CHAPTER 4 (CONCLUSION) 17REFERENCE
 [1] E. J. Cockayne, P. A. Jr. Dreyer, S. M., Hedetniemi, and S. T. Hedetniemi, Roman domination in graphs, Discrete Mathmatics 278 (2004) 11-22.[2] I. Stewart, Defend the Roman Empire, Scientific American 281 (1999) 136-139.[3] E. J. Cockayne, P. A. Jr. Dreyer, S. M., Hedetniemi, and S. T. Hedetniemi, Roman domination in graphs, Discrete Mathmatics 278 (2004) 11-22.[4] C.-H. Hsu, C.-S. Liu, and S.-L. Peng, Roman domination on block graphs, Proceedings of the 22nd Workshop on Combinatorial Mathematics and Computation Theory (2005) 188-191[5] M. Liedloff, T. Kloks, J. Liu, and S.-L. Peng, Roman domination over somegraph classes, WG 2005, LNCS 3787 (2005) 103-114.[6] H.S. Chao, F.R. Hsu, R.C.T. Lee, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, Discrete Applied Mathematics 102 (2000) 159-173[7] C.S. ReVelle, K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (7) (2000) 585–594.[8]M.C. Golumbic, Algorithm Graph Teory and Perfect Graphs (Academic Press, New York, 1980).[9]Y. D. Liang, C. Rhee, S. K. Dhall and S. Lakshmivarahan, A new approach for the domination problem on permutation graphs, Information Processing Letters 37(1991)219-224[10]Y. Daniel Liang, Teaching Dynamic Programming Techniques Using Permutation Graphs, ACM 1995 0-89791-693-x/95/0003[11]C. Rhee, Y. D. Liang, S. K. Dhall and S. Lakshmivarahan, An O(m+n) algorithm for finding minimum weight dominating set in permutation graphs, SIAM J. on Computing, to appear, 1994.[12] M. A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 225-234.[13] M. A. Henning, Defending the Roman Empire from multiple attacks, Discrete Mathematics 271 (2003) 101-115.[14]Henning Fernau, Roman Domination: A Parameterized Perspective, SOFSEM 2006, LNCS 3831,pp.262-271, 2006
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 圖形測度性質之研究：樞紐點與冪次圖

 無相關期刊

 1 雲端系統上之有效虛擬機分配機制 2 在二分排列圖上的支配數問題 3 廣播支配問題之研究 4 生物資訊探勘問題之研究 5 全基因體高密度多層單標籤索引之建立及其應用 6 植基於龜殼與AMBTC的影像篡改偵測與恢復機制 7 基於角度與距離影像比對技術開發出高效率的蛋白質結構比對方法 8 基因資料庫中相似與不相似型樣搜尋技術之研究 9 蛋白質二級結構特徵分析與預測 10 限制條件多序列比對之平行演算法 11 原核生物蛋白質功能之系統分析 12 在無線網路上使用組合融合方法處理接續互通和負載平衡問題 13 分群演算法在蛋白質交互作用網路之應用 14 GAM-Cluster: 以GPU加速MetaCluster5.0 15 以貼序法找出牙周病患之口腔環境基因體樣本可能含有的毒力因子分析

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