圓環弧圖上的羅馬支配問題

The Roman Domination Problem on Circular-Arc Graphs

廖俊崴(Chun-Wei Liao)

指導教授 ： 陳健輝 ； 林清池

國立臺灣大學/電機資訊學院/資訊工程學系/碩士(2023年)

https://doi.org/10.6342/NTU202302534

摘要

圖 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.

並列關鍵字

Roman domination ； Domination problems ； circular-arc graph

參考文獻

[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.