請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/70275完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝 | |
| dc.contributor.author | Keng-Chien Chang | en |
| dc.contributor.author | 張耿健 | zh_TW |
| dc.date.accessioned | 2021-06-17T04:25:07Z | - |
| dc.date.available | 2020-08-16 | |
| dc.date.copyright | 2018-08-16 | |
| dc.date.issued | 2018 | |
| dc.date.submitted | 2018-08-15 | |
| dc.identifier.citation | [1] H. A. Harutyunyan and C. Jimborean, “New heuristic for message broadcasting in networks,” Proceedings of the 28th IEEE International Conference on Advanced Information Networking and Applications, pp. 517–524, 2014.
[2] H. Harutyunyan, A. Liestman, J. Peters, and D. Richards, “Broadcasting and gossiping, in: Handbook of graph theory, second edition,” Chapman and Hall/CRC, pp. 1477–1494, 2013. [3] H. Harutyunyan and A. Liestman, “Improved upper and lower bounds for kbroadcasting,”Networks, vol. 37, pp. 94–101, 2001. [4] H. Harutyunyan and A. Liestman, “k-broadcasting in trees,” Networks, vol. 38,pp. 163–168, 2001. [5] H. Harutyunyan, A. Liestman, K. Makino, and T. Shermer, “Nonadaptive broadcastingin trees,” Networks, vol. 57, pp. 157–168, 2011. [6] H. Harutyunyan, A. Liestman, and B. Shao, “A linear algorithm for finding the kbroadcastcenter of a tree,” Networks, vol. 53, pp. 287–292, 2009. [7] H. Harutyunyan and B. Shao, “An efficient heuristic for broadcasting in networks,”J. Parallel Distrib. Comput., vol. 66, no. 1, pp. 68–76, 2006. [8] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi, “Information of dissemination in trees.,” SIAM J. Comput., vol. 10, no. 4, p. 692–701, 1981. [9] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi, “Information dissemination in trees with nonuniform edge transmission times,” IEEE Trans. Comput., vol. 40, no.10, pp. 1174–1177, 1991. [10] G. Kortsarz and D. Peleg, “Approximation algorithms for minimum time broadcast.,”SIAM J. Discrete Math, vol. 8, pp. 401–427, 1995. [11] M.Elkin and G. Kortsarz, “Sublogarithmic approximation for telephone multicast.,”J. Comput. Syst. Sci., vol. 72, pp. 648–659, 2006. [12] U. Feige, D. Peleg, P. Raghavan, and E. Upfal, “Randomized broadcast in networks.,”Proc. 1st SIGAL Int. Symp. Algorithms, vol. 450, pp. 128–137, 1990. [13] P. Fraigniaud and S. Vial, “Approximation algorithms for broadcasting and gossiping.,”J. Parallel Distrib. Comput., vol. 43, pp. 47–55, 1997. [14] R. Beier and J. Sibeyn, “A powerful heuristic for telephone gossiping.,” Proc. 7th Int. Colloquium Structural Info Comm. Complexity, pp. 17–36, 2000. [15] H. Harutyunyan and B. Shao, “An efficient heuristic for broadcasting in networks.,”J. Parallel Distrib. Comput., vol. 66, pp. 68–76, 2006. [16] Y.-H. Su, C.-C. Lin, and D. Lee, “Broadcasting in weighted trees under the postal model,” Theor. Comput. Sci., vol. 621, pp. 73–81, 2016. [17] C.-H. Tsou, G.-H. Chen, H.-I. Yu, and C.-C. Lin, “The broadcast median problem in heterogeneous postal model,” J. Comb Optim, vol. 25, no. 4, pp. 602–616, 2013. [18] A. N. C. Kang and D. A. Ault, “Some properties of a centroid of a free tree,” Information Processing Letters, vol. 4, no. 1, pp. 18–20, 1975. [19] A. J. Goldman, “Optimal center location in simple networks,” Transportation Science, vol. 5, pp. 212–221, 1971. [20] S. Peng and W.-T. Lo, “Efficient algorithms for finding a core of a tree with a specified length,” Journal of Algorithms, vol. 20, pp. 445–458, 1996. [21] P. M. Fenwick, “A new data structure for cumulative frequency tables,” SOFTWARE PRACTICE AND EXPERIENCE, vol. 24, no. 3, pp. 327–336, 1994. [22] A. Tamir, “An O(pn^2) algorithm for the p-median and related problems on tree graphs,” Operations Research Letters, vol. 19, pp. 59–64, 1996. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/70275 | - |
| dc.description.abstract | 本論文提出一 O(n√n log n) 時間複雜度的演算法，來解決傳遞規則是異質郵寄模型的加權樹狀結構下的廣播雙重心問題。首先證明樹的中點是最佳的廣播中心，其次發現在廣播雙重心下，必定有一條邊是不會用到的，因此對每條邊兩側的子樹去計算廣播時間，最後應用樹狀數組的技巧，把子樹重複的部分合併計算而達到較佳的時間複雜度。 | zh_TW |
| dc.description.abstract | This thesis presents an O(n√n log n) time complexity algorithm for solving broadcast 2-medians problem on a weighted tree under the postal model. First,we prove that a centroid is the broadcast 1-median. Next, we can observe
that in broadcast 2-median, there exists an unused edge, so we compute thebroadcast time for the subtree of each edge in both side. Finally, for best time complexity, binary indexed tree data structure is used to compute the broadcast time, which can save time from recomputing the duplicated part of subtree. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T04:25:07Z (GMT). No. of bitstreams: 1 ntu-107-R05922092-1.pdf: 979374 bytes, checksum: 7e7e223b17b201be42cb27bc844fad81 (MD5) Previous issue date: 2018 | en |
| dc.description.tableofcontents | 誌謝 v
摘要 vii Abstract ix 1 Introduction 1 1.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Notations and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Finding Broadcast 1-Median 5 3 Finding Broadcast 2-Medians 11 3.1 The case of subtrees without centroid . . . . . . . . . . . . . . . . . . . 12 3.2 The case of subtrees with centroid . . . . . . . . . . . . . . . . . . . . . 23 4 Conclusion and Future Work 35 Bibliography 37 | |
| 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 | centroid | en |
| dc.subject | binary indexed tree | en |
| dc.subject | step function | en |
| dc.subject | heterogeneous postal model | en |
| dc.subject | broadcast medain | en |
| dc.title | 加權樹上基於郵政模型的廣播雙重心問題 | zh_TW |
| dc.title | Finding Broadcast 2-Medians on a Weighted Tree under
the Postal Model | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 106-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 林清池 | |
| dc.contributor.oralexamcommittee | 張貴雲,傅榮勝 | |
| dc.subject.keyword | 廣播重心,異質郵寄模型,中點,樹狀數組,階躍函數, | zh_TW |
| dc.subject.keyword | broadcast medain,heterogeneous postal model,centroid,binary indexed tree,step function, | en |
| dc.relation.page | 39 | |
| dc.identifier.doi | 10.6342/NTU201802639 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2018-08-15 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-107-1.pdf 未授權公開取用 | 956.42 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。