權重區塊圖上的成對支配點問題

Abstract

本論文提出一演算法來解決權重區塊圖上的成對支配 點問題。試想一由點與線構成的圖,支配集是圖上的點 構成的點集合,而圖上每個不在支配集裡的點都會至少 與一在支配集裡的點相鄰,如此就構成了支配集。而對 於一圖上的成對支配點集,就是既滿足支配集的定義又 滿足支配集裡點形成的誘導子圖上,點兩兩成對。在一 圖上無數成對支配集中,如何找到一成對支配集且此集 合點的數量為無數成對支配點中最少的,就是成對支配 點問題。此外,對於一區塊圖上的每一個點,我們都賦 予它一權重,如此在權重區塊圖上的成對支配點問題就 是在一點有權重的區塊圖上,找到一點的數量為最小且 點權重加總也為最小的成對支配點集合。在本論文中, 提出了 O(m + n) 時間複雜度的眼算法來解決這個問題。

AdominatingsetofagraphG=(V,E)isasubsetS ⊆V if every vertex not in S is adjacent to a vertex in S. A domi- nating set S of a graph G is called a paired dominating set if the induced subgraph G[S] contains a perfect matching. The paired domination problem is to find a minimum size of a paired dominating set of a graph. Suppose moreover that ev- ery vertex v ∈ V associate with a weight w(v). The weight paired domination problem is to find a paired dominating set S such that its total weight W(S) = ∑{w(v) : v ∈ S} is min- imum. In this paper, we provide an dyanmic programming algorithm with O(m + n)-time for the weight paired domina- tion problem on block graphs.