臺灣博碩士論文加值系統

近年來有一個相當熱門的支配圖(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
圖列 iv
CHAPTER 1 (INTRODUCTION) 1
CHAPTER 2 (PRELIMINARIES) 5
CHAPTER 3 (ALGORITHM) 9
CHAPTER 4 (CONCLUSION) 17
REFERENCE

[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 some
graph 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