加權樹上基於郵政模型的廣播雙重心問題

Abstract

本論文提出一 O(n√n log n) 時間複雜度的演算法，來解決傳遞規則是異質郵寄模型的加權樹狀結構下的廣播雙重心問題。首先證明樹的中點是最佳的廣播中心，其次發現在廣播雙重心下，必定有一條邊是不會用到的，因此對每條邊兩側的子樹去計算廣播時間，最後應用樹狀數組的技巧，把子樹重複的部分合併計算而達到較佳的時間複雜度。

This thesis presents an O(n√n log n) time complexity algorithm for solving broadcast 2-medians problem on a weighted tree under the postal model. First,we prove that a centroid is the broadcast 1-median. Next, we can observe that in broadcast 2-median, there exists an unused edge, so we compute thebroadcast time for the subtree of each edge in both side. Finally, for best time complexity, binary indexed tree data structure is used to compute the broadcast time, which can save time from recomputing the duplicated part of subtree.