摘要
本論文設計一演算法來解決權重仙人掌圖上的完全支 配點問題。給定一張由點與邊所組成的圖，支配集為圖 上的點所構成的一個點集合，而圖上每個不在支配集裡 的點皆至少與一個在支配集裡的點相鄰，稱此點集合為 支配集。對於一張圖上的完全支配點集，則是圖上的每 個點都至少會與一個在支配集裡的點相鄰。一張圖的完 全支配集並不唯一，如何找到一完全支配集且此點集合 的點數量為所有的完全支配點中最少的，就是完全支配 點問題。此外，若對於一仙人掌圖上的每一個點都賦予 一權重，在此權重仙人掌圖上的完全支配點問題就是在 一有權重的仙人掌圖上找到一完全支配集，此集合的點 權重加總為所有的完全支配點集合中最小的。本論文提 出了一演算法來解決這個問題，此演算法的時間複雜度 為O(m + n)。
並列摘要
A dominating set of a graph G = (V ,E) is a subset S in V if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is said to be a total dominating set if every vertex is adjacent to a vertex in S. The total domination problem is to find a minimum size of a total dominating set of a graph. In addition, suppose that every vertex v belongs to V is associated with a weight w(v). The weight total domination problem is to find a total dominating set S such that its total weight W(S) = Σ{w(v) : v is in S} is minimum. In this paper, we provide a dyanmic programming algorithm for the weight total domination problem on cactus graphs. The time complexity of this algorithm is O(m + n).