Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48915
Title: | 權重仙人掌圖上的完全支配點問題 Total Domination in Weighted Cactus Graph |
Authors: | Wei-Chieh Kao 高偉傑 |
Advisor: | 陳健輝 |
Keyword: | 圖論,完全支配點問題,仙人掌圖,權重圖,動態規劃, graph theory,total domination problem,cactus graph,weighted graph,dynamic programming, |
Publication Year : | 2016 |
Degree: | 碩士 |
Abstract: | 本論文設計一演算法來解決權重仙人掌圖上的完全支
配點問題。給定一張由點與邊所組成的圖,支配集為圖 上的點所構成的一個點集合,而圖上每個不在支配集裡 的點皆至少與一個在支配集裡的點相鄰,稱此點集合為 支配集。對於一張圖上的完全支配點集,則是圖上的每 個點都至少會與一個在支配集裡的點相鄰。一張圖的完 全支配集並不唯一,如何找到一完全支配集且此點集合 的點數量為所有的完全支配點中最少的,就是完全支配 點問題。此外,若對於一仙人掌圖上的每一個點都賦予 一權重,在此權重仙人掌圖上的完全支配點問題就是在 一有權重的仙人掌圖上找到一完全支配集,此集合的點 權重加總為所有的完全支配點集合中最小的。本論文提 出了一演算法來解決這個問題,此演算法的時間複雜度 為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). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48915 |
DOI: | 10.6342/NTU201603532 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-105-1.pdf Restricted Access | 878.2 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.