加權樹上基於郵政模型的p­-廣播中心問題

Abstract

本論文提出一 O(n^2) 時間複雜度的演算法，來解決傳遞規則是異質郵寄模型的加權樹狀結構下的廣播 p 中心問題。首先，我們發現最少所需的廣播中心數量和時間限制的關係是一個單調非遞增階梯函數，透過這個觀察我們可以用二分搜尋法來搜尋結果；所以我們先提出一 O(n) 時間複雜度的演算法來計算在時間限制為 t 時，最少所需要的廣播中心數量為多少；然而如果直接在實數軸上做搜尋的話將會有無限多組解，因此我們進一步利用削減與搜尋的技巧保留最佳解所在的範圍，達到較佳的時間複雜度。

This thesis presents an O(n^2) time complexity algorithm for solving broadcasting p­center problem on weighted trees under the postal model. First of all, we observe that the relation between minimum number of centers needed and time constraint is a monotonic non­increasing step function. By this observation, we can binary search on real axis to find the solution. Therefore, we then proposed an O(n) time complexity algorithm to determine the minimum number of centers needed to broadcast within the time constraint t; However, there will be infinite candidates of solutions. Thus, we further use prune and search to maintain a interval which contains the optimal solution. Consequently, we have an O(n^2) time complexity algorithm.