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

Abstract

圖形G上的羅馬支配是指為圖中的每個點分配一個值為0、1 或 2。每個分配值為0的點至少有一個分配值為2的鄰居點。羅馬支配的權重是所有點的分配值之總和。

圓弧圖G由圓上的一組弧F定義，其中每個弧對應於G中的一個頂點。頂點v和u是相鄰的，若且唯若它們對應的弧在圓上相交時。羅馬支配問題尋求一個羅馬支配函數，其總權重在所有可能的分配中是最小的。

在過去有人已經提出了一個O(n^2)的算法來解決圓環圖上的羅馬支配問題，本論文目標是開發一種線性算法，來有效地解決圓弧圖上的羅馬支配問題。

Roman domination in a graph G refers to an assignment of labels 0, 1, or 2 to each vertex. Vertices labeled 0 must have at least one neighbor labeled 2. The weight of a Roman domination is the sum of all vertex labels. A circular-arc graph G is defined by a set F of arcs on a circle, where each arc corresponds to a vertex in G. Vertices v and u are adjacent if and only if their corresponding arcs intersect on the circle. The Roman domination problem seeks a Roman domination function with the minimum total weight across all possible assignments.

In previous research, an O(n^2) algorithm was proposed to solve the Roman Domination Problem on circular-arc graphs. The objective of this thesis is to develop a linear-time algorithm to efficiently address the Roman Domination Problem on circular-arc graphs.