臺灣博碩士論文加值系統

p -中心點問題基本上是要找出一個圖G中的p個頂點，作為建置某種設施的地點。此問題的目的是要讓所有使用者從所在之頂點到達最近設施頂點間距離，最遠者要最短。令G(V, E, l, w)為一個n頂點及m條邊的圖，其中每個頂點均有權重且每條邊均有長度。給定一個圖G(V, E, l, w)，有一個名為具權重連通p-中心點問題 (簡稱WCpC問題)，此問題是p -中心點問題的一個實用變型。WCpC問題的目的除了要讓所有使用者從所在之頂點到達最近設施頂點間加權距離，最遠者要最短之外，尚要求選出的p個建置設施的頂點所誘發的子圖在G中必須是連通的。當每個頂點v的權重值w(v)均為1時，此問題將被簡稱為CpC 問題。首先，我們證明了CpC 問題在平面圖及區間圖皆是NP-困難的。第二，針對樹形圖我們設計了兩個演算法來解決WCpC問題。它們的時間複雜度分別為O(pn)及O(n log2n)。此外，如果所有頂點的權重值最多只有k種可能，本論文則提出了另一個時間複雜度為O(kn)的演算法。接下來，我們探討了將此問題延伸到具禁選頂點的圖上，我們稱為具禁選點的WCpC問題 (簡稱FWCpC問題) 。我們證明了FWCpC問題在樹形圖上也存在O(n log2n)時間複雜度的演算法。最後，在頂點權重值與邊長之長度值均為1的區間圖上，本論文設計了一個O(n)的演算法來解決此問題。

The essential p-Center problem is to determine a set of p vertices of a graph G for building facilities. The objective is to minimize the maximum access distance of clients at all vertices. Let G(V, E, l, w) be a n-vertex and m-edge graph with lengths on edges and weights on vertices. Given a graph G(V, E, l, w), a practical variant, called the Weighted Connected p-Center problem (the WCpC problem), is to find a p-center of G such that the maximum weighted access distance of clients at all vertices is minimized under the additional restriction in which requires the selected p-center induce a connected subgraph of G. If w(v) = 1, for all v in V, then the problem is abbreviated as the CpC problem. We first prove that the CpC problem is NP-Hard on planar graphs and interval graphs, respectively. Second, we propose two algorithms for the WCpC problem on trees with time-complexities O(pn) and O(n log2n), respectively, by different approaches. Meanwhile, if w(v) ? C, for all v in V, where C is a set of k numbers, for some small integer k, then another algorithm with time-complexity O(kn) is proposed. Next, the extension to graphs with forbidden vertices, called the Forbidden Weighted Connected p-Center problem (the FWCpC problem) is discussed. We show that the FWCpC problem can be also solved in O(n log2n) time. Finally, we propose an O(n) time algorithm for the FCpC problem on interval graphs with unit vertex-weights and unit edge-lengths.

誌謝 I
摘要 II
Abstract III
Table of Contents IV
Table of Figures V
Table of Tables VII
1. Introduction and Motivation 1
2. The CpC problem is NP-Hard on Planar Graphs and Interval Graphs 7
3. The WCpC problem on Trees 14
3-1. An O(pn)-Time Algorithm 14
3-2. An O(kn)-Time Algorithm 24
3-3. An O(n log2n)-Time Algorithm 29
4. The FWCpC problem on Trees 36
5. The Forbidden Connected p-Center Problem on Interval Graphs 47
6. Conclusions 57
References 59

[1]Barrett C., Hunt III H. B., Marathe M. V., Ravi S. S., Rosenkrantz D. J., Stearns R. E., and Thakur M. (2007), Predecessor existence problems for finite discrete dynamical systems, Theoretical Computer Science, Vol. pp. 386, 3-37.
[2]Ben-Moshe B., Bhattacharya B., Shi Q., and Tamir A. (2007), Efficient algorithms for center problems in cactus networks, Theoretical Computer Science, Vol. 378, pp. 237–252.
[3]Burkard R. E. and Dollani Helidon. (2003), Center problems with pos/neg weights on tree, European Journal of Operational Research, Vol. 145, Iss. 3, pp. 483-495
[4]Cheng T. C. E., Kang L., and Ng C. T. (2007), An improved algorithm for the p-center problem on interval graphs with unit lengths, Computers & Operations Research, Vol. 34, pp. 2215-2222.
[5]Daskin M. S. (1995), Networks and Discrete Location, Models, Algorithms, and Applications, John Wiley & Sons, Inc., New York.
[6]Daskin M. S. (2008), What you should know about location modeling, Naval Research Logistics, Vol. 55, pp. 283-294.
[7]Frederickson G. (1991), Parametric search and locating supply centers in tree, in Proceedings of workshop on algorithms and data structures, pp. 299–319.
[8]Frederickson G. N. and Johnson D. B. (1983), Finding kth paths and p-centers by generating and searching good data structures, J. Algebra, Vol. 4, pp. 61–80.
[9]Gavril F. (1974), The intersection graphs of subtrees in tree are exactly the chordal graphs, Journal of Combinatorial Theory Series B, Vol. 16, pp. 47-56.
[10]Garey M. R. and Johnson D. S. (1978), Computers and Intractability: A Guide to the Theory of NP-Completeness, Bell Laboratories, Murray Hill, Freeman & Co., N. J.
[11]Golumbic M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, Inc., New York.
[12]Gould R. (1988), Graph Theory, The Benjamin/Cummings Publishing Company, Inc., Menlo Park, California.
[13]Hunt III H. B., Marathe M. V., Radhakrishnan, and Stearns R. E. (1998), The complexity of planar counting problems, SIAM Journal on Computing, Vol. 27, No. 4, pp. 1142-1167.
[14]Kariv O and Hakimi S. L. (1979), An algorithmic approach to network location problems I: the p-centers, SIAM Journal of Applied Mathematics, Vol. 37, pp. 514–538.
[15]Lan Y-F, Wang Y-L, and Suzuki H. (1999), A linear-time algorithm for solving the center problem on weighted cactus graphs, Information Processing Letters, Vol. 71, pp. 205-212.
[16]Megiddo N. (1983), Linear-time algorithms for linear programming in R3 and related problems, SIAM Journal on Computing, Vol. 12, No. 4, pp. 759-776.
[17]Megiddo N., Tamir A., Zemel E., and Chandrasekaran R. (1981), An O(n log2 n) algorithm for the kth longest path in a tree with application to location problems, SIAM Journal of Computing, Vol. 10, pp. 328–337.
[18]ReVelle C. S., Eiselt H. A., and Daskin M. S. (2008), A bibliography for some fundamental problem categories in discrete location science, European Journal of Operational Research, Vol. 184, pp. 817-848.
[19]Rose D. J., Tarjan R. E., and Lueker G. S. (1976), Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, Vol. 5, pp. 266-283.
[20]Yen W. C-K and Chen C-T. (2007), The p-Center Problem with Connectivity Constraint, Applied Mathematical Sciences, Vol. 1, no. 27, pp. 1311-1324.