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

Finding k-broadcast centers under postal model

楊孟翰(Meng-Han Yang)

指導教授 ： 陳健輝

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201602247

摘要

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

關鍵字

廣播問題 ； k-廣播中心點 ； 演算法 ； 權重樹 ； 郵政模型

並列摘要

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.

並列關鍵字

broadcasting problem ； k-broadcast ； algorithm ； weighted tree ； postal model

參考文獻

[21] S. Lee and J. Ventura. Construction of time-relaxed c-broadcast

in heterogeneous networks. SIAM J. Comput., 30(2):347–358,

broadcasting in almost trees and partial k-trees. In proceedings of

the 15th Annual Symposium on Theoretical Aspects of Computer

Science, pages 432–443, 1998.