臺灣博碩士論文加值系統

為設施找出最佳的安放位置是一個日常生活中真實而且重要的問題。因此這類問題被各領域的學者們廣泛的討論與研究，尤其在傳輸與通訊領域為最甚。由於存在各種型態的設施與不同的最佳化條件，因此有許許多多的放置問題 (location problem) 被提出來探討。諸多最佳化的條件當中以『離心率』 (eccentricity) 與『距離和』 (distancesum) 兩者被使用的頻率最高。離心律指的是網路當中離設施最遠的點與設施的距離，而距離和指的是網路上所有點到設施的距離加總。大部份放置問題在廣意圖 (general graph) 上都被證明是NP-Hard，因此學者紛紛把注意力集中在一些特別的圖上。其中以樹狀圖 (tree) 受到最多的討論。這類的問題引人之處在於除了本身具有高度的實用性外，有許多的問題到目前為止仍然沒有有效率的解決方法，尤其是平行演算法方面，十分缺乏，本論文即以這方面作為研究的主題。
這篇論文討論的是樹狀圖上的 p 中心問題 (p-center problem)。所謂的 p 中心問題是希望在放置 p 個設施後，離心率為最小，這是在放置理論 (Location Theory) 上最有名也最重要的問題之一。循序演算法方面經過前人多年的研究已經有了非常好的結果，但是在平行演算法方面，則十分欠缺。原因是現有的循序演算法都是利用動態規劃 (dynamic programming) 設計，很難平行化。目前所知的平行結果都作了一個非常不合理的假設: 樹狀圖上每一個邊的長度都是 1。在這個假設下，目前最好的結果是在 CREW PRAM 上，使用 O(log2 nloglog n) 時間與 O(nlog2 nloglog n) 的計算成本 (cost)。本篇論文提出了第一個可適用於一般樹狀圖上的平行演算法。這個新方法在 CREW PRAM 上，使用 O(log3 n) 時間與 O(nlog2 n) 的計算成本。與前人的結果相比，除了更具一般性外，計算成本也更為節省。

Let T=(V, E) be a free tree with vertex set V and edge set E. Let n=|V|. Each eE has a non-negative length. In this thesis, we first present an algorithm on the CREW PRAM for solving the V/V/r-dominating set problem on T, where r0 is a real number. The presented algorithm requires O(log^2 n) time using O(nlog n) work. Applying this algorithm as a procedure for testing feasibility, we then solve the V/V/p-center problem on the CREW PRAM in O(log^3 n) time using O(nlog^2 n) work, where p>1 is an integer. Previously, He and Yesha had proposed parallel algorithms on the CREW PRAM for special cases of the V/V/r-dominating set and the V/V/p-center problems, in which r is an integer and the lengths of all edges are 1. Their V/V/r-dominating set algorithm requires O(log nloglog n) time using O(nlog nloglog n) work; and their V/V/p-center algorithm requires O(log^2 nloglog n) time using O(nlog^2 nloglog n) work. As compared with He and Yesha''s results, ours are more general and more efficient from the aspect of work.
Key words: trees, r-dominating sets, p-centers, network location theory, parallel algorithms, CREW PRAM.

1 Introduction 1
2 Sequential Algorithm for the r-Dominating Set Problem 4
3 Centroid Decomposition 7
4 Sequential Algorithm on Paths 10
4.1 Preliminaries 10
4.2 Sequential Algorithm on Paths 14
5 Parallel Algorithm on Trees 17
5.1 Preliminaries 17
5.2 Parallel Algorithm on Trees 22
6 Parallel Algorithm for the p-Center Problem 25
7 Conclusion and Future Work 27
Reference 28

[1]. R. Chandrasekaran and A. Tamir, “An O((nlog p)2) algorithm for the continuous p-center problem on a Tree,” SIAM Journal on Algebraic and Discrete Methods, vol. 1, pp. 370-375, 1980.
[2]. R. Chandrasekaran and A. Tamir, “Polynomially bounded algorithms for locating p-centers on a tree,” Mathematical Programming, vol. 22, pp. 304-315, 1982.
[3]. R. Cole, “Slowing down sorting networks to obtain faster sorting algorithms,” Journal of the ACM, vol. 34, pp. 200-208, 1987.
[4]. R. Cole and U. Vishkin, “Approximate parallel scheduling. part I: the basic technique with applications to optimal parallel list ranking in logarithmic time,” SIAM Journal on Computing, vol. 17, pp. 128-142, 1988.
[5]. R. Cole and U. Vishkin, “The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time,” Algorithmica, vol. 3, pp. 329-346, 1988.
[6]. G. N. Frederickson, “Parametric search and locating supply centers in trees,” in Proceedings of the Second Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 1991.
[7]. G. N. Frederickson and D. B. Johnson, “Finding kth paths and p-centers by generating and searching good data structures,” Journal of Algorithms, vol. 4, pp. 61-80, 1983.
[8]. B. Gavish and S. Sridhar, “Computing the 2-median on tree networks in O(nlg n) time,” Networks, vol. 26, pp. 305-317, 1995.
[9]. A. J. Goldman, “Optimal center location in simple networks,” Transportation Science, vol. 5, pp. 212-221, 1971.
[10]. A. J. Goldman, “Minmax location of a facility in an undirected tree graph,” Transportation Science, vol. 6, pp. 407-418, 1972.
[11]. S. L. Hakimi, “Optimal distribution of switching centers in communication networks and some related graph theoretical problems,” Operations Research, vol. 13, pp. 462-475, 1965.
[12]. S. L. Hakimi, E. F. Schmeichel, and M. Labbé, ”On locating path- or tree-shaped facilities on networks,” Networks, vol. 23, pp. 543-555, 1993.
[13]. G. Y. Handler, “Minimax location of a facility in an undirected tree network,” Transportation Science, vol. 7, pp. 287-293, 1973.
[14]. G. Y. Handler, “Finding two-centers of a tree: the continuous case,” Transportation Science, vol. 12, pp. 93-106, 1978.
[15]. G. Y. Handler and P. Mirchandani, Location on Networks, MIT Press, Cambridge, MA, 1979.
[16]. X. He and Y. Yesha, “Binary tree algebraic computation and parallel algorithms for simple graphs,” Journal of Algorithms, vol. 9, pp. 92-113, 1988.
[17]. X. He and Y. Yesha, “Efficient parallel algorithms for r-dominating set and p-center problems on trees,” Algorithmica, vol. 5, pp. 129-145, 1990.
[18]. J. JáJá, An Introduction to Parallel Algorithm, Addison-Wesley, Reading, MA, 1992.
[19]. O. Kariv and S. L. Hakimi, “An algorithmic approach to network location problems. I: The p-centers,” SIAM Journal on Applied Mathematics, vol. 37, pp. 513—538, 1979.
[20]. O. Kariv and S. L. Hakimi, “An algorithmic approach to network location problems. II: The p-medians,” SIAM Journal on Applied Mathematics, vol. 37, pp. 539—560, 1979.
[21]. N. Megiddo, “Applying parallel computation algorithms in the design of serial algorithms,” Journal of the ACM, vol. 30, pp. 852-865, 1983.
[22]. N. Megiddo, A Tamir, E. Zemel and R. Chandrasekaran, “An O(nlog² n) algorithm for the k-th longest path in a tree with applications to location problems,” SIAM Journal on Computing, vol. 10, pp. 328-337, 1981.
[23]. N. Megiddo and A. Tamir. “New results on the complexity of p-center problems,” SIAM Journal on Computing, vol. 12, pp. 751-758, 1983.
[24]. E. Minieka, “The optimal location of a path or tree in a tree network,” Networks, vol. 15, pp. 309-321, 1985.
[25]. P. J. Slater, “R-domination in graphs,” Journal of the ACM, vol. 23, pp. 446-450, 1976.
[26]. A. Tamir, “An O( pn2) algorithm for the p-median and other related problems on tree graphs,” Operation Research Letters, vol. 19, pp. 59—64, 1996.
[27]. A. Tamir, “The k-centrum multi-facility location problem,” Discrete Applied Mathematics, vol. 109, pp. 293-307, 2001.