具時間限制的廣播中心問題

Broadcast Centers in Trees with Time Constraints

黃煜翔(Yu-Shiang Huang)

指導教授 ： 陳健輝

共同指導教授 ： 林清池(Ching-Chi Lin)

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

https://doi.org/10.6342/NTU.2015.02302

摘要

本論文提出一 O(n) 時間複雜度的演算法來解決樹狀結構上的廣播中心點問題，使廣播中心點的數量最少。廣播按照異質郵寄模型的規則進行，需在時間限制內完成。

關鍵字

廣播中心點問題 ； 時間限制 ； 異質郵寄模型 ； 樹狀結構 ； 貪進法

並列摘要

In this thesis, we present a O(n)-time exact algorithm to find a broadcast strategy such that broadcasting can be completed within the time constraint and the number of centers is minimal. The given graph is a tree and broadcasting is under the heterogeneous postal model.

並列關鍵字

broadcast center problem ； time constraint ； heterogeneous postal model ； trees ； greedy method

參考文獻

[1] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, “Message multicasting in heterogeneous networks,” SIAM Journal on Computing, vol.

[3] A. Bar-Noy and S. Kipnis, “Multiple message broadcasting in the

[4] J.-m. Koh and D.-w. Tcha, “Information dissemination in trees with

nonuniform edge transmission times,” IEEE Transactions on Computers, vol. 40, no. 10, pp. 1174–1177, 1991.

[6] R. Ravi, “Rapid rumor ramification: approximating the minimum broadcast time,” in Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 202–213.