請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/4659完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
| dc.contributor.author | Yu-Shiang Huang | en |
| dc.contributor.author | 黃煜翔 | zh_TW |
| dc.date.accessioned | 2021-05-14T17:44:48Z | - |
| dc.date.available | 2017-07-29 | |
| dc.date.available | 2021-05-14T17:44:48Z | - |
| dc.date.copyright | 2015-07-29 | |
| dc.date.issued | 2015 | |
| dc.date.submitted | 2015-07-24 | |
| dc.identifier.citation | [1] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, “Message multicasting in heterogeneous networks,” SIAM Journal on Computing, vol.
30, no. 2, pp. 347–358, 2000. [2] A. Bar-Noy and S. Kipnis, “Designing broadcasting algorithms in the postal model for message-passing systems,” Mathematical Systems Theory, vol. 27, no. 5, pp. 431–452, 1994. [3] A. Bar-Noy and S. Kipnis, “Multiple message broadcasting in the postal model,” Networks, vol. 29, no. 1, pp. 1–10, 1997. [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. [5] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi, “Information dissemination in trees,” SIAM Journal on Computing, vol. 10, no. 4, pp. 692–701, 1981. [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. [7] G. Kortsarz and D. Peleg, “Approximation algorithms for minimumtime broadcast,” SIAM Journal on Discrete Mathematics, vol. 8, no. 3, pp. 401–427, 1995. 49 [8] M. Elkin and G. Kortsarz, “Sublogarithmic approximation for telephone multicast: path out of jungle,” in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete algorithms, 2003, pp. 76– 85. [9] R. Beier and J. F. Sibeyn, A Powerful Heuristic for Telephone Gossiping. Citeseer, 2000. [10] H. A. Harutyunyan and B. Shao, “An efficient heuristic for broadcasting in networks,” Journal of Parallel and Distributed Computing, vol. 66, no. 1, pp. 68–76, 2006. [11] P. Scheuermann and G. Wu, “Heuristic algorithms for broadcasting in point-to-point computer networks,” IEEE Transactions on Computers, vol. 100, no. 9, pp. 804–811, 1984. [12] H. A. Harutyunyan and E. Maraachlian, “On broadcasting in unicyclic graphs,” Journal of Combinatorial Optimization, vol. 16, no. 3, pp. 307–322, 2008. [13] H. A. Harutyunyan, G. Laza, and E. Maraachlian, “Broadcasting in necklace graphs,” in Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering, 2009, pp. 253–256. [14] H. A. Harutyunyan and E. Maraachlian, “Broadcasting in fully connected trees,” in Proceedings of the 15th IEEE International Conference on Parallel and Distributed Systems, 2009, pp. 740–745. [15] P. Bhabak and H. A. Harutyunyan, “Broadcast problem in hypercube of trees,” Lecture Notes in Computer Science : Frontiers in Algorithmics, vol. 8497, pp. 1–12, 2014. [16] E. Maraachlian, “Optimal broadcasting in treelike graphs,” PhD thesis, Concordia University, 2010. 50 [17] Y.-H. Su, C.-C. Lin, and D. T. Lee, “Broadcasting in heterogeneous tree networks,” Lecture Notes in Computer Science : Computing and Combinatorics, vol. 6196, pp. 368–377, 2010. [18] A. Farley, S. Hedetniemi, S. Mitchell, and A. Proskurowski, “Minimum broadcast graphs,” Discrete Mathematics, vol. 25, no. 2, pp. 189–193, 1979. [19] A. M. Farley, “Broadcast time in communication networks,” SIAM Journal on Applied Mathematics, vol. 39, no. 2, pp. 385–390, 1980. [20] A. M. Farley and A. Proskurowski, “Broadcasting in trees with multiple originators,” SIAM Journal on Algebraic Discrete Methods, vol. 2, no. 4, pp. 381–386, 1981. [21] A. L. Liestman and J. G. Peters, “Broadcast networks of bounded degree,” SIAM Journal on Discrete Mathematics, vol. 1, no. 4, pp. 531– 540, 1988. [22] C.-H. Tsou, G.-H. Chen, H.-I. Yu, and C.-C. Lin, “The broadcast median problem in heterogeneous postal model,” Journal of Combinatorial Optimization, vol. 25, no. 4, pp. 602–616, 2013. [23] P. Fraigniaud and E. Lazard, “Methods and problems of communication in usual networks,” Discrete Applied Mathematics, vol. 53, no. 1, pp. 79–133, 1994. [24] H. Grigoryan, “Problems related to broadcasting in graphs,” PhD thesis, Concordia University, 2013. [25] S. M. Hedetniemi, S. T. Hedetniemi, and A. L. Liestman, “A survey of gossiping and broadcasting in communication networks,” Networks, vol. 18, no. 4, pp. 319–349, 1988. 51 [26] J. Hromkovič, R. Klasing, B. Monien, and R. Peine, “Dissemination of information in interconnection networks (broadcasting & gossiping),” Combinatorial Network Theory, pp. 125–212, 1996. [27] H. A. Harutyunyan, A. L. Liestman, and B. Shao, “A linear algorithm for finding the k-broadcast center of a tree,” Networks, vol. 53, no. 3, pp. 287–292, 2009. [28] C.-H. Tsou, G.-H. Chen, and C.-C. Lin, “Broadcasting in heterogeneous tree networks with uncertainty,” Lecture Notes in Computer Science : Algorithms and Computation, vol. 7074, pp. 200–209, 2011. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/4659 | - |
| dc.description.abstract | 本論文提出一 O(n) 時間複雜度的演算法來解決樹狀結構上的廣播中心點問題，使廣播中心點的數量最少。廣播按照異質郵寄模型的規則進行，需在時間限制內完成。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-14T17:44:48Z (GMT). No. of bitstreams: 1 ntu-104-R01922090-1.pdf: 701324 bytes, checksum: 7082ef6dcd30a8733446f3e5bb9b11ed (MD5) Previous issue date: 2015 | en |
| dc.description.tableofcontents | 口試委員會審定書 iii
誌謝 v Acknowledgements vii 摘要 ix Abstract xi 1 Introduction 1 1.1 Broadcast Problem and Models . . . . . . . . . . . . . 1 1.2 Main Results and Thesis Organization . . . . . . . . . 2 2 Preliminaries 3 2.1 Notations and Definitions . . . . . . . . . . . . . . . . 3 2.2 Related Works . . . . . . . . . . . . . . . . . . . . . . 5 3 A Linear-Time Algorithm 7 3.1 Algorithm Description . . . . . . . . . . . . . . . . . . 7 3.2 Finding SUCC(v) and b_time(v) . . . . . . . . . . . . 9 3.3 Evaluatng spare(v) . . . . . . . . . . . . . . . . . . . . 11 xiii 3.4 A Non-Sorting Method . . . . . . . . . . . . . . . . . . 12 3.5 Time Complexity . . . . . . . . . . . . . . . . . . . . . 16 4 Correctness 19 4.1 Minimum Unused Edges and Broadcast Time . . . . . 20 4.2 Earliest Spare Time . . . . . . . . . . . . . . . . . . . 23 4.3 Correctness of the Algorithm . . . . . . . . . . . . . . 24 5 Two Illustrative Examples 29 5.1 The First Example . . . . . . . . . . . . . . . . . . . . 29 5.2 The Second Example . . . . . . . . . . . . . . . . . . . 39 6 Conclusion 47 Bibliography 49 | |
| dc.language.iso | en | |
| dc.subject | 時間限制 | zh_TW |
| dc.subject | 樹狀結構 | zh_TW |
| dc.subject | 貪進法 | zh_TW |
| dc.subject | 異質郵寄模型 | zh_TW |
| dc.subject | 廣播中心點問題 | zh_TW |
| dc.subject | greedy method | en |
| dc.subject | broadcast center problem | en |
| dc.subject | time constraint | en |
| dc.subject | heterogeneous postal model | en |
| dc.subject | trees | en |
| dc.title | 具時間限制的廣播中心問題 | zh_TW |
| dc.title | Broadcast Centers in Trees with Time Constraints | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 103-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 林清池(Ching-Chi Lin) | |
| dc.contributor.oralexamcommittee | 胡家正(Chia-Cheng Hu),周信宏(Hsin-Hung Chou) | |
| dc.subject.keyword | 廣播中心點問題,時間限制,異質郵寄模型,樹狀結構,貪進法, | zh_TW |
| dc.subject.keyword | broadcast center problem,time constraint,heterogeneous postal model,trees,greedy method, | en |
| dc.relation.page | 52 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2015-07-24 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-104-1.pdf | 684.89 kB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。