Abstract
在一個圖形上，討論如何找出一些新設施之最佳設置地點的問題，我們稱之為「設施放置問題」。以設施種類而言，目前被討論的有點狀 (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)。