請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49873完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
| dc.contributor.author | Meng-Han Yang | en |
| dc.contributor.author | 楊孟翰 | zh_TW |
| dc.date.accessioned | 2021-06-15T11:54:01Z | - |
| dc.date.available | 2016-08-24 | |
| dc.date.copyright | 2016-08-24 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-08-10 | |
| dc.identifier.citation | [1] A. Bar-Noy, S. Guha, J.Naor, and B.Schieber. Message multicasting
in heterogeneous networks. SIAM J. Comput., 30(2):347–358, 2000. [2] A. Bar-Noy and S.Kipnis. Designing broadcasting algorithms in the postal model for message-passing systems. Math. Systems Theorey, 27(5):431–452, 1994. [3] R. Beier and J. Sibeyn. A powerful heuristic for telephone gossiping. In Proc. 7th Int Colloquium Structural Info Comm. Complexity, pages 17–36, Laquila, Italy, 2000. [4] A. Dessmark, A. Lingas, H. Olsson, and H. Yamamoto. Optimal 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. [5] A. Farley and A. Proskurowski. Broadcasting in trees with multiple originators. J. Parallel and Distrib. Comput., 2(4):381–386, 2006. [6] U. Feige, D. peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Proc. 1st SIGAL Int Symp. Algorithms, 450:128– 137, 1990. [7] P. Fraigniaud and E. Lazard. Methods and problems of com- munication in usual networks. Discrete Appl Math, 53:79–133, 1994. [8] P. Fraigniaud and S. Vial. Approximation algorithms for broadcasting and gossiping. J. Parallel Distrib. Comput., 43:47–55, 1997. [9] M. Grigni and D. Peleg. Tight bounds on minimum broadcast networks. SIAM J Discrete Math, 4:207–222, 1991. [10] H. Harutyunyan and A. Liestman. k-broadcasting in trees. Networks, 38:163–168, 2001. [11] H. Harutyunyan and A. Liestman. On the monotonicity of the broadcast function. Discrete Math, 262:149–157, 2003. [12] H. Harutyunyan and B. Shao. An efficient heuristic for broadcasting in networks. J Parallel Distrib. Comput., 66:68–76, 2006. [13] H. A. Harutyunyan and A. L. Liestman. Improved upper and lower bounds for k-broadcasting. Networks, 37(2):94–101, 2001. [14] H. A. Harutyunyan, A. L. Liestman, and B. Shao. A linear algorithm for finding the k-broadcast center of a tree. Networks, 53(3):287–292, 2009. [15] S. M. Hedetniemi, S. T. Hedetniemi, and A. L. Liestman. Survey of gossiping and broadcasting in communication networks. Networks, 18(4):319–349, 1988. [16] J. Hromkovicˇ, R. Klasing, B. Monien, and R. Peine. Dissemination of information in interconnection networks. Combinatorial network theory, pages 125–212, 1995. [17] J. Hromkovicˇ, R. Klasing, A. Pelc, P. Ružicˇka, and W. Unger. Dissemination of information in communication networks: Broadcasting, gossiping, leader election, and fault-tolerance. Texts in Theoretical Computer Science, An EATCS Series, 2005. [18] A. Jakoby, R. Reischuk, and C. Shindelhauer. The complexity of broadcasting in planar and decomposable graphs. Discrete Appl Math, 83:179–206, 1998. [19] J.-M. Koh and D.-W. Tcha. Information dissemination in trees with nonuniform edge transmission times. IEEE Trans. Comput., 40(10):1174–1177, 1991. [20] G. Kortsarz and D. Peleg. Approximation algorithms for minimum time broadcast. SIAM J Discrete Math, 8:401–427, 1995. [21] S. Lee and J. Ventura. Construction of time-relaxed c-broadcast networks. In Telecommun Syst. 24, pages 47–59, 2003. [22] M.Elkin and G. Kortsarz. Sublogarithmic approximation for telephone multicast. J Comput. Syst. Sci, 72:648–659, 2006. [23] A. Shastri and S. Gaur. Multi-broadcasting in communication networks i:trees. In Proc. Int Symp. Commun., pages 167–170, Hsinchu, Taiwan, 1997. [24] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi. Information of dissemination in trees. SIAM J. Comput., 10(4):692–701, 1981. [25] Y.-H. Su, C.-C. Lin, and D. T. Lee. Broadcasting in weighted trees under the postal model. Theor. Comput. Sci., 621:73–81, 2016. [26] A. Tamir. An o(pn2) algorithm for the p-median and related problems on tree graphs. Operations Research Letters, 19(2):59–64, 1996. [27] C.-H. Tsou, G.-H. Chen, H.-I. Yu, and C.-C. Lin. The broadcast median problem in heterogeneous postal model. J. Comb. Optim, 25(4):602–616, 2013. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49873 | - |
| dc.description.abstract | 本論文提出一演算法來解決在郵政模型中的權重樹上找出k-廣播中心點以及最小廣播時間的問題。 給定一權重樹T=(V,E)，任兩點間每次傳送資訊前必須花費α時間建立連線，待連線建立後，即可開始傳送資訊不需等待其他點，邊的權重在此用來表示相鄰兩點間傳送資訊所需的時間。 k-廣播指的是每個點在廣播訊息給樹中相鄰點時，每單位時間α最高能夠同時與k個相鄰點建立連線。 在此論文中我們希望能夠找出這些k-廣播中心點，且這些點能夠使得廣播訊息給樹中所有點所花費的時間是最短的， 同時我們的演算法也會決定樹中所需的最小廣播時間。在這篇論文中，我們提出了一個O(n)時間複雜度的演算法來解決這個問題。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T11:54:01Z (GMT). No. of bitstreams: 1 ntu-105-R03922120-1.pdf: 702520 bytes, checksum: 15452fa5234e5488850d407344d60a78 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 試委員會審定書iii
誌謝v 摘要vii Abstract ix 1 Introduction 1 1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . 4 2 Algorithm k-BROADCAST 7 2.1 Terms and Definition . . . . . . . . . . . . . . . . . . . 7 2.2 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 An algorithm . . . . . . . . . . . . . . . . . . . . . . . 9 3 Correctness of Algorithm 11 4 Time complexity 21 4.1 Non-Sorting Labelled Method . . . . . . . . . . . . . . 21 4.2 k-BROADCAST algorithm in O(n)-time . . . . . . . . 23 5 Conclusion and Future work 27 Bibliography 29 | |
| dc.language.iso | en | |
| dc.subject | 郵政模型 | zh_TW |
| dc.subject | 演算法 | zh_TW |
| dc.subject | k-廣播中心點 | zh_TW |
| dc.subject | 權重樹 | zh_TW |
| dc.subject | 廣播問題 | zh_TW |
| dc.subject | weighted tree | en |
| dc.subject | k-broadcast | en |
| dc.subject | algorithm | en |
| dc.subject | postal model | en |
| dc.subject | broadcasting problem | en |
| dc.title | 基於郵政模型中的k-廣播中心點問題 | zh_TW |
| dc.title | Finding k-broadcast centers under postal model | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 林清池(Ching-Chi Lin),胡家正(Chia-Cheng Hu),周信宏(Hsin-Hung Chou) | |
| dc.subject.keyword | 廣播問題,k-廣播中心點,演算法,權重樹,郵政模型, | zh_TW |
| dc.subject.keyword | broadcasting problem,k-broadcast,algorithm,weighted tree,postal model, | en |
| dc.relation.page | 31 | |
| dc.identifier.doi | 10.6342/NTU201602247 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-08-11 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 未授權公開取用 | 686.05 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。