請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56811
標題: | 權重區段圖與權重圓弧圖上的成對支配點問題 Paired Domination on Weighted Interval Graphs and Circular-Arc Graphs |
作者: | Kuan-Lun Chen 陳冠綸 |
指導教授: | 陳健輝(Gen-Huey Chen) |
關鍵字: | 成對支配點問題,區段圖,圓弧圖,動態規劃, paired-domination problem,interval graphs,circular-arc graphs,dynamic programming, |
出版年 : | 2014 |
學位: | 碩士 |
摘要: | 對於圖G = (V, E)而言,點集合S為圖G的支配點集合若且唯若S是V的子集合,且每個在V中的點若非同時在S中,則必與某些在S中之點相鄰。若圖G由一個支配點集合所生成的誘導子圖擁有完美配對,則此支配點集合也被稱為圖G之成對支配點集合。成對支配點問題即為在圖G上找出一個基數最小的成對支配點集合S且S為V之子集合。同時,如果圖G為一權重圖,也就是說在點集V與另一權重集合中存在一個一對一對應關係,則此問題將在圖G上找出一個成對支配點集合S,滿足S中所有點的全中相加為最小且S為V之子集合。
在此篇論文中,給予一個權重區段圖G,其對應之區段模型已可取得且所有邊界點已排序,且令n與m分別為點和邊之數量。我們首先提出一個可在O(n)時間內找出一個在G上之最小權重成對支配點集合的演算法。接著我們進一步設計另一個演算法,來找出一個在已可取得弧形模型的權重圓弧圖上的最小權重成對支配點集合。經由延伸我們已找出在權重區段圖上的結果,該演算法可整體在O(n+m)時間內完成。 For a graph G = (V, E), a vertex set S is said to be a dominating set of G if and only if S $subseteq$ V and every vertex in V that not in S is adjacent to some vertices in S. The dominating set S is also said to be a paired-dominating set if the induced subgraph G[S] has a perfect matching. The paired-domination problem is to find the minimum-cardinality paired-dominating set S $subseteq$ V of G. And if G is a weighted graph, i.e. there exists a one-to-one corresponding between vertex set V and a weight set, then this problem is for finding a paired-dominating set S $subseteq$ V which sum of vertex weights in are minimum. In this paper, given a weighted interval graph G with available interval model whose all endpoints are sorted, and let n and m be the vertex number and edge number, respectively. We first propose an O(n)-time algorithm for finding a minimum-weight paired-dominating set of G. Further, we design another algorithm for finding a minimum-weight paired-dominating set of weighted circular-arc graphs whose arc model is available, which can run in O(n+m) time totally by extending our results on weighted interval graph. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56811 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 503.92 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。