李德財Lee, Der-Tsai臺灣大學:資訊工程學研究所高孟駿Kao, Mong-JenMong-JenKao2010-05-182018-07-052010-05-182018-07-052008U0001-0607200814143600http://ntur.lib.ntu.edu.tw//handle/246246/183624我們考慮在圖論上廣為人知的支配集問題，並將它加以推廣。所謂「有容量的支配集問題」是指在給定的圖上，尋找滿足每個點的容量限制(capacity)與需求限制(demand)的最小支配集。在這個問題模型中，每個點都有各自的容量和需求。容量(capacity)指的是，每份此頂點的實體(copy)，可以容納多少單位來自閉鄰點(closedeighborhood)的需求。而需求(demand)指的則是，此頂點需要多少單位來自閉鄰點的容量供給。此論文中，我們從演算法的觀點探討「有容量的支配集問題」在樹狀結構中的表現。在需求不可分割的模型裡，我們提供了線性時間複雜度的演算法；而對於需求可分割的問題模型，我們則提供了虛擬多項式時間(pseudo-polynomial time)的演算法。此之外，我們也証明，當需求可分割時，這個問題在樹狀結構上也是NP-完備，並進一步提供可任意逼近最佳解(polynomialime approximation scheme)的演算法。對於一般的圖，我們則提供以線性規劃的primal-dual為基礎的近似演算法。We consider a generalization of the well-known domination problem on graphs. The soft capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demand of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies that the demand of each vertex in is met by the capacities of vertices in D dominating it.n this thesis, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.Contents試委員會審定書....................................icknowledgement...................................iihinese Abstract....................................iiinglish Abstract....................................iv Introduction.1 Preliminaries...................................5 Capacitated Domination on Trees.1 Unsplittable Demand Model...........................7.2 NP-completeness for Splittable Demand Model................13.3 A Pseudo-polynomial Time Algorithm for Splittable Demand Model....16.3.1 The Relaxed Knapsack Problem....................21 Approximation Algorithms for Splittable Demand Model.1 Approximation on Trees.............................23.2 Approximation on General Graphs.......................27 Conclusion.1 Discussion.....................................32.2 Future Work...................................34ibliography 34 Pseudo Codes 39.1 Algorithm MCDUT...............................39.2 Algorithm MCDST................................43.3 Algorithm MCDAWG..............................46 Implementation 48application/pdf601552 bytesapplication/pdfen-US演算法圖論支配集algorithmgraph theorydominationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183624/1/ntu-97-R95922078-1.pdf