- 學位論文
權重區段圖與權重圓弧圖上的成對支配點問題
Paired Domination on Weighted Interval Graphs and Circular-Arc Graphs
摘要
對於圖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.