基於郵政模型中的k-廣播中心點問題

Abstract

本論文提出一演算法來解決在郵政模型中的權重樹上找出k-廣播中心點以及最小廣播時間的問題。 給定一權重樹T=(V,E)，任兩點間每次傳送資訊前必須花費α時間建立連線，待連線建立後，即可開始傳送資訊不需等待其他點，邊的權重在此用來表示相鄰兩點間傳送資訊所需的時間。 k-廣播指的是每個點在廣播訊息給樹中相鄰點時，每單位時間α最高能夠同時與k個相鄰點建立連線。 在此論文中我們希望能夠找出這些k-廣播中心點，且這些點能夠使得廣播訊息給樹中所有點所花費的時間是最短的， 同時我們的演算法也會決定樹中所需的最小廣播時間。在這篇論文中，我們提出了一個O(n)時間複雜度的演算法來解決這個問題。

The broadcasting problem is to find a broadcast center such that the transmission time from the center to all vertices is minimized. In this thesis, we consider k-broadcasting in weighted tree under postal model. In postal model, we have to create a links which cost -time before broadcasting a message, after the link created, the transmission begin without waiting other transmission complete, the term k-broadcast means the process of creating link from one vertex to at most k adjacent vertices can process simultaneously. In this thesis, the algorithm computes the set of k-broadcast centers and determines the broadcast time of the weighted tree in O(n) time.