電機資訊學院: 資訊工程學研究所指導教授: 陳健輝楊孟翰Yang, Meng-HanMeng-HanYang2017-03-032018-07-052017-03-032018-07-052016http://ntur.lib.ntu.edu.tw//handle/246246/275375本論文提出一演算法來解決在郵政模型中的權重樹上找出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.702520 bytesapplication/pdf論文公開時間: 2016/8/24論文使用權限: 同意有償授權(權利金給回饋學校)廣播問題k-廣播中心點演算法權重樹郵政模型broadcasting problemk-broadcastalgorithmweighted treepostal modelthesis10.6342/NTU201602247http://ntur.lib.ntu.edu.tw/bitstream/246246/275375/1/ntu-105-R03922120-1.pdf