臺灣博碩士論文加值系統

在一個圖形中，每個點可以控制它自己及所有和它相鄰的點。Ｖ是某圖形
的點集合，對Ｖ的子集合Ｓ，如果Ｖ中的每個點都至少被Ｓ中的兩個點控
制，則Ｓ稱為此圖形的雙重控制集。圖形的雙重控制集問題是要找一個圖
形的最小雙重控制集的大小。在這篇論文中，我們首先證明雙重控制集問
題對任意圖形、弦圖、分裂圖、二分圖均是ＮＰ－ｃｏｍｐｌｅｔｅ，我
們也提出兩個對樹之雙重控制集問題的線性演算法；其中一個是用標號計
算法，另一個是用動態規劃法。動態規劃的方法可以推廣到加權的雙重控
制集問題，而標號計算法可推廣到在強弦圖上找ｋ重控制集的線性演算法
。

Each vertex of a graph G=(V,E) is said to dominate itself and
all vertices adjacent to it. A set D .lhkeq. V is a double
dominating set of G if each vertex of V is dominated by at
least two vertices in D. The double domination problem is to
find the smallest size of a double dominating set of a given
graph G, which is called the double domination number dd(G). In
this paper, we first prove that the double domination problem
is NP-complete for general graphs, chordal graphs, split
graphs, and bipartite graphs. We also give two linear-time
algorithm for the problem in trees, one is by a labeling method
and the other is by the dynamic programming approach. The
dynamic programming method is then generalized to one that
solves the weighted double domination problem in trees. The
labeling method is then generalized to a linear-time algorithm
for the k-tuple domination problem in strongly chordal graphs.