在權重樹上尋找具時間限制的廣播中心問題

Abstract

本論文提出一個演算法來解決在郵政模型中的權重樹上找出一個具時間限制的廣播中心問題。給定一權重樹 T = (V,E) 及時間限制 t ，在郵政模型的規則下傳播，邊的權重在此用來表示相鄰兩點間傳送資訊所需的時間，時間限制 t 指的是所有點接受到訊息的時間不能超出 t 。在此論文中我們希望能夠找出一個最佳的廣播中心，使得廣播訊息給樹中所有點所花費的時間總和最小，且所有的點都能在時間 t 內接收到訊息，同時我們的演算法也會得到整顆樹的最佳廣播時間，以及最佳的廣播順序。在這篇論文中我們結合了動態規劃法還有匈牙利演算法，提出一個 O(min(t,n) · n4) 時間複雜度的演算法來解決這個問題。

We propose the problem of finding a broadcast median on a weighted tree with time con- straint under the postal model. Given a weighted tree T = (V,E) with time constraint t, the overall delay of a vertex v ∈ V (T ), is the minimum sum of the transmission time required to send a message from v to all vertices in T , and the medain is the node that has the minimum overall delay. Time constraint t denotes that all nodes in T should receive the message before time t.In this thesis, weproposean O(min(t,n)·n4) time complexity algorithm that uses dynamic programming and Hungarian Algorithm to find a median in T with time constraint.