- 學位論文
Finding the Conditional Location of a Median Path on a Tree
在樹狀圖上尋找條件式重心路徑之演算法
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
The facility location problem is concerned with the finding of the optimal location in a network for setting up new service facilities. Based on the type of the facilities, there are three kinds of facilities considered in the literature: point-shaped, path-shaped, and tree-shaped facilities. Path-shaped and tree-shaped facilities are also called extensive facilities. Recently, there has been an increasing interest in the study of the problem of setting up new facilities on a network where some existing facilities are already located. Such problems are called conditional location problems. The study of conditional location problems is both of theoretical interest and practical importance, and many papers dealing with conditional location problems have appeared in the literature. In this dissertation, we examine the problem of locating a median path of limited length on a tree under the condition that some existing facilities are already located. The existing facilities may be located at any subset of vertices. Upper and lower bounds are proposed for both the discrete and continuous models. In the discrete model, a median path is not allowed to contain partial edges. In the continuous model, a median path may contain partial edges. The proposed upper bounds for these two models are O(nlog n) and O(nlog nalpha(n)), respectively. They improve the previous known bounds from O(nlog^2 n) and O(n^2), respectively. The proposed lower bounds are both omega(nlog n).
並列摘要
在一個圖形上，討論如何找出一些新設施之最佳設置地點的問題，我們稱之為「設施放置問題」。以設施種類而言，目前被討論的有點狀 (point-shaped)、條狀 (path-shaped)、以及樹狀 (tree-shaped) 三種設施。其中條狀及樹狀設施又被稱為延展式設施(extensive facilities)。近年來為了符合現實環境下的實際狀況，在設施放置問題這個研究領域裡，有一類新的研究主題越來越被重視，稱為「條件式設施放置問題」(conditional location problems)。這一類問題主要是在討論如何在已存在一些既有設施的條件下，另外尋找新設施的最佳設置地點。這一類問題的探討，不論就理論研究或實際應用而言，都具有相當的重要性，因此，有越來越多不同的條件式設施放置問題被提出與討論。 這篇論文研究的是在已存在一些既有設施的樹狀圖 (tree graph) 上，尋找滿足長度限制的重心路徑 (median path)。根據實際應用的需要，我們分別考慮了兩種模式下的重心路 徑，分別是 discrete model 以及 continuous model。在 discrete model 下，所選擇的重心路徑必須由完整的 edge 所組成，而在 continuous model 下，選擇的重心路徑可以包含非 完整的 edge (partial edge)。對這兩種模式，我們都提出了比既有方法更快速的演算法。在 discrete model 下，我們把這個問題的時間複雜度由原本的 O(nlog^2 n) 降到 O(nlog n)；而在 continuous model 上的時間也由原本的 O(n^2) 加快到 O(nlog n alpha(n))。另外我們也證明了這個問題的時間下界 (lower bound) 在這兩種模式下同樣都是 omega(nlog n)。
並列關鍵字
location theory ； medians ； conditional location problems ； trees ； paths ； extensive facilities ； algorithms參考文獻
[1] E. A. Albacea, "Parallel algorithm for finding a core of a tree network," Information Processing Letters, vol. 51, pp.223-226, 1994.
[2] S. Alstrup, J. Holm, K. D. Lichtenberg, and M. Thorup, "Maintaining information in fully dynamic trees with top trees," ACM Transactions on Algorithms, vol. 1, no. 2, pp. 243-264, 2005.
[4] I. Averbakh and O. Berman, "Algorithms for path medi-centers of a tree," Computers & Operations Research, vol. 26, pp. 1395-1409, 1999.
[5] R. I. Becker, I. Lari, and A. Scozzari. "Algorithms for central-median paths with bounded length on trees," European Journal of Operational Research, vol. 179, pp. 1208-1220, 2007.
[6] R. I. Becker and Y. Perl, "Finding the two-core of a tree," Discrete Applied Mathematic, vol. 11, pp. 103-113, 1985.