完整後設資料紀錄
DC 欄位語言
dc.contributor.author劉佳芸en_US
dc.contributor.authorLiu, Chia Yunen_US
dc.contributor.author張鎮華en_US
dc.contributor.authorGerard J. Changen_US
dc.date.accessioned2014-12-12T02:14:10Z-
dc.date.available2014-12-12T02:14:10Z-
dc.date.issued1994en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#NT830507014en_US
dc.identifier.urihttp://hdl.handle.net/11536/59643-
dc.description.abstract在一個圖形中,每個點可以控制它自己及所有和它相鄰的點。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.zh_TW
dc.language.isoen_USen_US
dc.subject控制; 雙重控制集; 多重控制集; 強弦圖zh_TW
dc.subjectdominate; double dominating set; k-tuple dominating set; strongly chordal graphen_US
dc.title圖形的雙重控制集問題zh_TW
dc.titleThe Double Domination Problem in Graphsen_US
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
顯示於類別:畢業論文