加權樹上基於電話模型的廣播重心問題

Abstract

本論文提出一個O(nlogn)時間複雜度的演算法，來解決傳遞規則是電話模型的加權樹狀結構下的廣播重心問題。首先，我透過證明一為最佳傳遞順序的策略來達到最小的廣播時間。接著，我在演算法設計上運用了動態規劃的概念，發現可以使用迴圈方式，按照順序來計算，快速地得到各個點分別當廣播起點所需花費的廣播時間；並且以往回取值的方式來實作，利用記憶體空間減少計算上的重複，有效地降低計算上的時間複雜度。

For the case of broadcasting on the structure of a tree which is composed of non-uniform edges and weighted vertices in a telephone-like communication system. I showed that a simple ordering policy achieves the minimum overall delay for any given source v and proposed an O(nlogn) time complexity algorithm using dynamic programming technique to determine a set of broadcast medians on such a weighted tree.