標題: 圖形的雙重控制集問題
The Double Domination Problem in Graphs
作者: 劉佳芸
Liu, Chia Yun
張鎮華
Gerard J. Chang
應用數學系所
關鍵字: 控制; 雙重控制集; 多重控制集; 強弦圖;dominate; double dominating set; k-tuple dominating set; strongly chordal graph
公開日期: 1994
摘要: 在一個圖形中,每個點可以控制它自己及所有和它相鄰的點。V是某圖形 的點集合,對V的子集合S,如果V中的每個點都至少被S中的兩個點控 制,則S稱為此圖形的雙重控制集。圖形的雙重控制集問題是要找一個圖 形的最小雙重控制集的大小。在這篇論文中,我們首先證明雙重控制集問 題對任意圖形、弦圖、分裂圖、二分圖均是NP-complete,我 們也提出兩個對樹之雙重控制集問題的線性演算法;其中一個是用標號計 算法,另一個是用動態規劃法。動態規劃的方法可以推廣到加權的雙重控 制集問題,而標號計算法可推廣到在強弦圖上找k重控制集的線性演算法 。 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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT830507014
http://hdl.handle.net/11536/59643
Appears in Collections:Thesis