圖形的雙重控制集問題

Abstract

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