請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/60272
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
dc.contributor.author | Po-Hsun Huang | en |
dc.contributor.author | 黃柏勳 | zh_TW |
dc.date.accessioned | 2021-06-16T10:14:36Z | - |
dc.date.available | 2020-08-21 | |
dc.date.copyright | 2020-08-21 | |
dc.date.issued | 2020 | |
dc.date.submitted | 2020-08-07 | |
dc.identifier.citation | [1] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi, “Information of dissemination in trees,” SIAM Journal on Computing, vol. 10, no. 4, pp. 692–701, 1981. [2] J. Koh and D. Tcha, “Information dissemination in trees with nonuniform edge transmission times,” IEEE Transactions on Computers, vol. 40, no. 10, pp. 1174–1177, 1991. [3] R. Gandhi, Y.A. Kim, S. Lee, J. Ryu, and P.J. Wan, “Approximation algorithms for data broadcast in wireless networks,” IEEE Transactions on Mobile Computing, vol. 11, no. 7, pp. 1237–1248, 2012. [4] R. Ravi, “Rapid rumor ramification: approximating the minimum broadcast time,” in Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 202–213, 1994. [5] G. Kortsarz and D. Peleg, “Approximation algorithms for minimumtime broadcast,” SIAM Journal on Discrete Mathematics, vol. 8, no. 3, pp. 401–427, 1995. [6] A. BarNoy, S. Guha, J. Naor, and B. Schieber, “Message multicasting in heterogeneous networks,” SIAM Journal on Computing, vol. 30, no. 2, pp. 347–358, 2000. [7] M. Elkin and G. Kortsarz, “Sublogarithmic approximation for telephone multicast: path out of jungle,” in Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete algorithms, pp. 76–85, 2003. [8] B. Puspal, Approximation Algorithms for Broadcasting in Simple Graphs with Intersecting Cycles. PhD thesis, Concordia University, 2014. [9] P. Bhabak and H. A. Harutyunyan, “Constant approximation for broadcasting in kcycle graph,” in Algorithms and Discrete Applied Mathematics, pp. 21–32, 2015. [10] R. Beier, J. F. Sibeyn, and J. F. Sibeyn, “A powerful heuristic for telephone gossiping,” 2000. [11] 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. [12] P. Scheuermann and G. Wu, “Heuristic algorithms for broadcasting in pointtopoint computer networks,” IEEE Transactions on Computers, vol. 100, no. 9, pp. 804–811, 1984. [13] H. A. Harutyunyan and C. Jimborean, “New heuristic for message broadcasting in networks,” in Proceedings of the 28th IEEE International Conference on Advanced Information Networking and Applications, pp. 517–524, 2014. [14] H. A. Harutyunyan and E. Maraachlian, “On broadcasting in unicyclic graphs,” Journal of Combinatorial Optimization, vol. 16, no. 3, pp. 307–322, 2008. [15] 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, pp. 253–256, 2009. [16] H. A. Harutyunyan and E. Maraachlian, “Broadcasting in fully connected trees,” in Proceedings of the 15th IEEE International Conference on Parallel and Distributed Systems, pp. 740–745, 2009. [17] P. Bhabak and H. A. Harutyunyan, “Broadcast problem in hypercube of trees, Lecture Notes in Computer Science : Frontiers in Algorithmics, vol. 8497, pp. 1–14, 2014. [18] E. Maraachlian, Optimal broadcasting in treelike graphs. PhD thesis, Concordia University, 2010. [19] A. Dessmark, A. Lingas, H. Olsson, and H. Yamamoto, “Optimal broadcasting in almost trees and partial ktrees,” in Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 432–443, 1998. [20] H. Harutyunyan, A. Liestman, and B. Shao, “A linear algorithm for finding the kbroadcast center of a tree,” Networks, vol. 53, pp. 287–292, 2009. [21] H. Harutyunyan, A. Liestman, and B. Shao, “Designing broadcasting algorithms in the postal model for messagepassing systems,” Mathematical Systems Theory, vol. 27, pp. 431–452, 1994. [22] Y.H. Su, C.C. Lin, and D. Lee, “Broadcasting in heterogeneous tree networks,” Lecture Notes in Computer Science : Computing and Combinatorics, vol. 6196, pp. 368–377, 2010. [23] 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. [24] A. Farley, S. Hedetniemi, S. Mitchell, and A. Proskurowski, “Minimum broadcast graphs,” Discrete Mathematics, vol. 25, no. 2, pp. 189–193, 1979. [25] A. M. Farley, “Broadcast time in communication networks,” SIAM Journal on Applied Mathematics, vol. 39, no. 2, pp. 385–390, 1980. [26] 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. [27] 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. [28] P. Fraigniaud and E. Lazard, “Methods and problems of communication in usual networks,” Discrete Applied Mathematics, vol. 53, no. 1, pp. 79–133, 1994. [29] H. Grigoryan, Problems related to broadcasting in graphs. PhD thesis, Concordia University, 2013. [30] 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. [31] J. Hromkovicˇ, R. Klasing, B. Monien, and R. Peine, “Dissemination of information in interconnection networks (broadcasting gossiping),” Combinatorial Network Theory, pp. 125–212, 1996. [32] 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/60272 | - |
dc.description.abstract | 本論文提出一 O(n^2) 時間複雜度的演算法,來解決傳遞規則是異質郵寄模型的加權樹狀結構下的廣播 p 中心問題。首先,我們發現最少所需的廣播中心數量和時間限制的關係是一個單調非遞增階梯函數,透過這個觀察我們可以用二分搜尋法來搜尋結果;所以我們先提出一 O(n) 時間複雜度的演算法來計算在時間限制為 t 時,最少所需要的廣播中心數量為多少;然而如果直接在實數軸上做搜尋的話將會有無限多組解,因此我們進一步利用削減與搜尋的技巧保留最佳解所在的範圍,達到較佳的時間複雜度。 | zh_TW |
dc.description.abstract | This thesis presents an O(n^2) time complexity algorithm for solving broadcasting pcenter problem on weighted trees under the postal model. First of all, we observe that the relation between minimum number of centers needed and time constraint is a monotonic nonincreasing step function. By this observation, we can binary search on real axis to find the solution. Therefore, we then proposed an O(n) time complexity algorithm to determine the minimum number of centers needed to broadcast within the time constraint t; However, there will be infinite candidates of solutions. Thus, we further use prune and search to maintain a interval which contains the optimal solution. Consequently, we have an O(n^2) time complexity algorithm. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T10:14:36Z (GMT). No. of bitstreams: 1 U0001-0707202018395500.pdf: 974105 bytes, checksum: 2a98568faa6c1839d006dca7aa83f260 (MD5) Previous issue date: 2020 | en |
dc.description.tableofcontents | 誌謝 iv 摘要 v Abstract vi 1 Introduction 1 1.1 The postal model 2 1.2 The broadcasting pcenter problem 3 2 Preliminaries 5 2.1 Notations and Definitions 5 2.2 Related Work 6 3 Finding Broadcasting Centers with Time Constraint 9 3.1 A LinearTime Algorithm 9 3.1.1 Algorithm Description 9 3.1.2 Determining succ(v) and b_time(v) 11 3.1.3 Determining pred(v) and Building Tables 15 3.1.4 Determining s_time(v) and Building Tables 17 3.2 Correctness Proof 20 3.3 Time Complexity 23 4 Broadcasting pCenter Problem 25 4.1 An Algorithm 25 4.1.1 Algorithm Description 25 4.1.2 Determining Intervals by succ(v) 27 4.1.3 Determining Intervals by pred(v) 28 4.2 Correctness Proof 29 4.3 Time Complexity 32 5 Conclusion and Future Work 34 Bibliography 35 | |
dc.language.iso | en | |
dc.title | 加權樹上基於郵政模型的p-廣播中心問題 | zh_TW |
dc.title | The Broadcasting p-Center Problem in a Weighted Tree under the Postal Model | en |
dc.type | Thesis | |
dc.date.schoolyear | 108-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 林清池(Ching-Chi Lin) | |
dc.contributor.oralexamcommittee | 傅榮勝(Jung-Sheng Fu),張貴雲(Guey-Yun Chang) | |
dc.subject.keyword | 廣播問題,p-中心,郵政模型,貪進法,動態規劃,削減與搜尋,二分搜尋法, | zh_TW |
dc.subject.keyword | broadcasting problem,p-center,postal model,greedy,dynamic programming,prune and search,binary search, | en |
dc.relation.page | 38 | |
dc.identifier.doi | 10.6342/NTU202001370 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2020-08-10 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-0707202018395500.pdf 目前未授權公開取用 | 951.27 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。