臺灣博碩士論文加值系統

一個圖形上的羅馬支配函數是一個函數f : V → {0, 1, 2}，它滿足
每一個對應到0 的點至少連到一個對應到2 的點。一個羅馬支配函數
的值就是指所有點對應值的總和。羅馬支配數就是一個圖形所有可能
的羅馬支配函數中最小的值。

羅馬支配問題來自於羅馬帝國派遣防衛部隊的策略，它主要的目
的是希望能用最少的部隊來保護帝國的城鎮跟村莊。如果這塊領域有
二隊軍隊鎮守時，那麼他們就可以保護鎮守的這塊領域跟所有鄰近的
城鎮。如果這地方只有一個軍隊鎮守，那麼他們就只可以保護自己。
羅馬支配問題在找出最少的軍隊數來保護整個羅馬帝國。在這篇論文
裡，我們討論羅馬支配問題在有限樹寬圖上的解決方法。

藉著輸入圖的nice tree decomposition，我們設計一個演算法從此
分解樹的葉節點處理到根節點，然後找到一個最佳解。因為樹寬是有
限的，所以每一個節點的執行時間是常數。於是我們設計出一個線性
時間的演算法來解決有限樹寬圖上的羅馬支配問題。

A Roman dominating function on a graph G = (V, E) is a function f : V → f(0, 1, 2) satisfying that every vertex u with f(u) = 0 has a neighbor v with f(v) = 2. The weight of the Roman dominating function f is the sum of f(v) for the vertices belonging to V. The Roman domination number of a graph G is the minimum weight of all possible Roman dominating functions on G.

The motivation of Roman domination is in assigning the minimum armies to protect all castles and villages at the age of Roman Empire. If two armies locate in an area, they can protect the area that they located and those areas that are their neighborhood. If an area is assigned an army, the army can protect only the place that they located. In this thesis, we consider the Roman domination problem on graphs of bounded treewidth.

By using a nice tree decomposition T of the input graph G, our algorithm works from leaves to the root of T. Since the treewidth of G is bounded, the time for computing the information of each node of T is constant. Thus, we obtain a linear-time algorithm for the Roman domination problem on bounded treewidth graphs.

Abstract i
Contents ii
List of Figures iii
List of Tables iv
1 Introduction 1
2 Preliminaries 5
3 A linear-time algorithm 10
4 Conclusion 25

[1] N. Betzler, R. Niedermeier, and J. Uhlmann, Tree decompositions of graphs: saving memory in dynamic programming, Discrete Optimization 3 (2006) 220-229.

[2] H. L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput. 25 (1996) 1305-1317.

[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] M. S. Chang, Effiecient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput. 27 (1998) 1671-1694.

[5] P. A. Jr. Dreyer, Applications and variations of domination in graphs, Ph.D. Thesis, Rutgers University, The State University of New Jersey, New Brunswick, NJ, 2000.

[6] D. Kratsch, Domination and total domination on asteroidal triple-free graphs, Discrete Applied Mathematics 99 (2000) 111-123.

[7] H. Fernau, Roman domination: A parameterized perspective, SOFSEM 2006, LNCS 3831 (2006).

[8] F. V. Fomin, D. Kratsch, and H. MÄuller, Algorithms for graphs with small octopus, Discrete Applied Mathematics, 134 (2004) 105-128.

[9] F. Nicolai and T. Szymczak, Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs, Networks 37 (2001) 117-128

[10] J. Guo, R. Niedermeier, and D. Raible, Improved algorithms and complexity results for power domination in graphs, FCT 2005, LNCS 3623 (2005) 172-184.

[11] M. A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 225-234.

[12] M. A. Henning, Defending the Roman Empire from multiple attacks, Discrete Mathematics 271 (2003) 101-115.

[13] M. A. Henning and S. T. Hedetniemi, Defending the Roman Empire-A new strategy, Discrete Mathematics 266 (2003) 239-251.

[14] 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

[15] T. Kloks, Treewidth{Computations and Approximations, LNCS 842, Springer, Berlin, 1994.

[16] T. Kloks, D. Kratsch, C. M. Lee, and J. Liu, Improved bottleneck domination algorithms, Discrete Applied Mathematics 154 (2006) 1578-1592.

[17] J. Kneis, D. Molle, S. Richter, and P. Rossmanith, Parameterized power domination complexity, Information Processing Letters 98 (2006) 145-149.

[18] M. Liedlo®, T. Kloks, J. Liu, and S.-L. Peng, Roman domination over some graph classes, WG 2005, LNCS 3787 (2005) 103-114.

[19] C. S. ReVelle and K. E. Rosing, Defenders imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585-594.

[20] I. Stewart, Defend the Roman Empire, Scientific American 281 (1999) 136-139.

[21] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in Graphs: Advanced Topics 191-231, Marcel Dekker, 1998.

[22] H. M. Xing, X. Chen, and X. G. Chen, A note on Roman domination in graphs, Discrete Mathematics 306 (2006) 3338-3340.