Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/15254Full metadata record
| ???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
|---|---|---|
| dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
| dc.contributor.author | Yu-Chen Chen | en |
| dc.contributor.author | 陳語宸 | zh_TW |
| dc.date.accessioned | 2021-06-07T17:28:59Z | - |
| dc.date.copyright | 2020-03-03 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-02-21 | |
| dc.identifier.citation | [1] A. Bar-Noy, S. Kipnis, and B. Schieber. Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems. Discrete Applied Mathematics, 100(1– 2):1–15, 2000.
[2] A. Bar-Noy and S. Kipnis. Multiple Message Broadcasting in the Postal Model. Networks, 29(1): 1–10, 1997. [3] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Message Multicasting in Heterogeneous Networks. SIAM J. Comput., 30(2): 347–358, 2000. [4] Keng-Chien Chang. Finding Broadcast 2-Medians on a Weighted Tree under the Postal Model. Master thesis, 2018. [5] H.-I. Y. C.-C. L. C.-H. Tsou, G-H. Chen. The broadcast median problem in heterogeneous postal model. J Comb Optim, 2013. [6] M.Elkin and G. Kortsarz. Sublogarithmic approximation for telephone multicast. J Comput. Syst. Sci, 72: 648–659, 2006. [7] J.-M. Koh and D.-W. Tcha. Information dissemination in trees with nonuniform edge transmission times. IEEE Trans. Comput., 40(10): 1174–1177, 1991. [8] Nimrod Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J Comput., 12: 759–776, 1983. [9] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi. Information of dissemination in trees. SIAM J. Comput., 1981. [10] D. L., Y.-H. Su, and C.-C. Lin. Broadcasting in weighted trees under the postal model. Theor. Comput, 2016. [11] Y.-H. Su, C.-C. Lin, and D. Lee. Broadcasting in Heterogeneous Tree Networks. Proc.16th Ann. Int. Conf. on Comp. comb(COCOON), 368–377. Springer-Verlag, 2010. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/15254 | - |
| dc.description.abstract | 本論文提出一個O(nlogn)時間複雜度的演算法，來解決傳遞規則是電話模型的加權樹狀結構下的廣播重心問題。首先，我透過證明一為最佳傳遞順序的策略來達到最小的廣播時間。接著，我在演算法設計上運用了動態規劃的概念，發現可以使用迴圈方式，按照順序來計算，快速地得到各個點分別當廣播起點所需花費的廣播時間；並且以往回取值的方式來實作，利用記憶體空間減少計算上的重複，有效地降低計算上的時間複雜度。 | zh_TW |
| dc.description.abstract | For the case of broadcasting on the structure of a tree which is composed of non-uniform edges and weighted vertices in a telephone-like communication system. I showed that a simple ordering policy achieves the minimum overall delay for any given source v and proposed an O(nlogn) time complexity algorithm using dynamic programming technique to determine a set of broadcast medians on such a weighted tree. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-07T17:28:59Z (GMT). No. of bitstreams: 1 ntu-109-R05922058-1.pdf: 1355098 bytes, checksum: 3aa5ebeb3d005e7de1edd95e86b5afae (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | 口試委員會審定書 iii
誌謝 v 摘要 vii Abstract ix 1 Introduction 1 1.1 Problem definition 3 1.2 Related work 4 1.3 Notations and definitions 5 2 The Proposed Algorithm 6 2.1 Preliminaries 6 2.2 Observations 8 2.3 A general formula 14 2.4 Computing overall delay differences 15 2.5 An algorithm for finding broadcast medians 17 3 Time Complexity 20 3.1 On the star topology 20 3.2 On the general tree 21 4 Concluding Remarks 23 References 24 | |
| dc.language.iso | zh-TW | |
| dc.subject | 動態規劃 | zh_TW |
| dc.subject | 廣播重心 | zh_TW |
| dc.subject | 電話模型 | zh_TW |
| dc.subject | 加權樹 | zh_TW |
| dc.subject | 廣播時間差通式 | zh_TW |
| dc.subject | broadcast median | en |
| dc.subject | dynamic programming | en |
| dc.subject | the general formula of overall delay differences | en |
| dc.subject | weighted vertex | en |
| dc.subject | non-uniform telephone model | en |
| dc.title | 加權樹上基於電話模型的廣播重心問題 | zh_TW |
| dc.title | Finding Broadcast Medians on a Weighted Tree under the Telephone Model | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 林清池(Ching-Chi Lin) | |
| dc.contributor.oralexamcommittee | 傅榮勝(Jung-Sheng Fu),張貴雲(Guey-Yun Chang) | |
| dc.subject.keyword | 廣播重心,電話模型,加權樹,廣播時間差通式,動態規劃, | zh_TW |
| dc.subject.keyword | broadcast median,non-uniform telephone model,weighted vertex,the general formula of overall delay differences,dynamic programming, | en |
| dc.relation.page | 25 | |
| dc.identifier.doi | 10.6342/NTU202000067 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2020-02-21 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| Appears in Collections: | 資訊工程學系 | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-109-1.pdf Restricted Access | 1.32 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.