請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73202
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳健輝 | |
dc.contributor.author | Guang-Che Yeh | en |
dc.contributor.author | 葉光哲 | zh_TW |
dc.date.accessioned | 2021-06-17T07:22:14Z | - |
dc.date.available | 2019-07-25 | |
dc.date.copyright | 2019-07-25 | |
dc.date.issued | 2018 | |
dc.date.submitted | 2019-07-03 | |
dc.identifier.citation | [1] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Message multicasting in heteroge- neous networks. SIAM Journal on Computing, 30(2):347–358, 2000.
[2] R. Beier and J. F. Sibeyn. A Powerful Heuristic for Telephone Gossiping. Citeseer, 2000. [3] P.BhabakandH.A.Harutyunyan.Broadcastprobleminhypercubeoftrees.Lecture Notes in Computer Science : Frontiers in Algorithmics, 8497:1–12, 2014. [4] R. Chandrasekaran and A. Tamir. An o((n log p)2 ) algorithm for the continuous p-center problem on a tree. SIAM Journal on Algebraic and Discrete Methods, 6(1):370–375, 1980. [5] 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, pages 76–85, 2003. [6] A. Farley, S. Hedetniemi, S. Mitchell, and A. Proskurowski. Minimum broadcast graphs. Discrete Mathematics, 25(2):189–193, 1979. [7] A.M.Farley.Broadcasttimeincommunicationnetworks.SIAMJournalonApplied Mathematics, 39(2):385–390, 1980. [8] A. M. Farley and A. Proskurowski. Broadcasting in trees with multiple originators. SIAM Journal on Algebraic Discrete Methods, 2(4):381–386, 1981. [9] P. Fraigniaud and E. Lazard. Methods and problems of communication in usual networks. Discrete Applied Mathematics, 53(1):79–133, 1994. [10] H. Grigoryan. Problems related to broadcasting in graphs. PhD thesis, Concordia University, 2013. [11] 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, pages 253–256, 2009. [12] 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. [13] H. A. Harutyunyan and E. Maraachlian. On broadcasting in unicyclic graphs. Jour- nal of Combinatorial Optimization, 16(3):307–322, 2008. [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, pages 740–745, 2009. [15] H. A. Harutyunyan and B. Shao. An efficient heuristic for broadcasting in networks. Journal of Parallel and Distributed Computing, 66(1):68–76, 2006. [16] S. M. Hedetniemi, S. T. Hedetniemi, and A. L. Liestman. A survey of gossiping and broadcasting in communication networks. Networks, 18(4):319–349, 1988. [17] J. Hromkovič, R. Klasing, B. Monien, and R. Peine. Dissemination of information in interconnection networks (broadcasting & gossiping). Combinatorial Network Theory, pages 125–212, 1996. [18] G. Kortsarz and D. Peleg. Approximation algorithms for minimum-time broadcast. SIAM Journal on Discrete Mathematics, 8(3):401–427, 1995. [19] A. L. Liestman and J. G. Peters. Broadcast networks of bounded degree. SIAM Journal on Discrete Mathematics, 1(4):531–540, 1988. [20] E. Maraachlian. Optimal broadcasting in treelike graphs. PhD thesis, Concordia University, 2010. [21] R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 202–213, 1994. [22] P. Scheuermann and G. Wu. Heuristic algorithms for broadcasting in point-to-point computer networks. IEEE Transactions on Computers, 100(9):804–811, 1984. [23] P.J.Slater,E.J.Cockayne,andS.T.Hedetniemi.Informationdisseminationintrees. SIAM Journal on Computing, 10(4):692–701, 1981. [24] Y.-H. Su, C.-C. Lin, and D. T. Lee. Broadcasting in heterogeneous tree networks. Lecture Notes in Computer Science : Computing and Combinatorics, 6196:368–377, 2010. [25] C.-H.Tsou,G.-H.Chen,andC.-C.Lin.Broadcastinginheterogeneoustreenetworks with uncertainty. Lecture Notes in Computer Science : Algorithms and Computation, 7074:200–209, 2011. [26] 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, 25(4):602– 616, 2013. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73202 | - |
dc.description.abstract | 本論文的主要目的是解決在郵政模型中權重樹上的 p-廣播中心問題。郵政模型是 眾多通訊網路模型之一,主要特色是任一節點想要將訊息傳給鄰居節點之前,必 須先花費 α 的時間先進行連線,而節點同時間只能和一個鄰居節點進行連線,但 節點可以同時與所有已經連線的鄰居節點傳遞訊息。這裡我們討論的通訊網路是 一個邊權重樹,其中邊的權重表示訊息經由這條邊傳遞不包含連線所需要花費的 時間。廣播中心是指那些一開始就擁有訊息的節點;廣播問題是要決定能使得網 路上所有節點都收到訊息的時間最短的廣播中心擺放位置;而 p 廣播中心問題是 指給定廣播中心的數量 p,要決定能使得網路上所有節點都收到訊息的時間最短 的 p 個廣播中心的擺放位置。
本論文提出兩個演算法:第一個演算法用來計算在給定一個時間限制 t 之下, 一個給定的樹狀網路最少需要幾個廣播中心、並且決定這些廣播中心的擺放位 置;第二個演算法用來計算在給定廣播中心數量 p 之下,一個給定的樹狀網路的 最短廣播時間。其中第一個演算法使用了貪進法以及動態規劃,依序由小子樹的 最佳解建構出大子樹的最佳解,時間複雜度為 O(n2)。第二個演算法先找出所求 最短廣播時間的候選集合,再將第一個演算法當作工具配合二分搜尋法,逐步 從候選集合中刪除掉不要的元素,最終找到所求最短廣播時間,時間複雜度為 O(n2 log n)。 利用第二個演算法得到最短廣播時間之後,再將其代回第一個演算法作為時間 限制,即可求得 p 個廣播中心的位置以及每個節點的傳訊給鄰居節點的順序,將 p-廣播中心問題解決。 | zh_TW |
dc.description.abstract | The main purpose of this thesis is to solve p-center problem in a weighted tree under the postal model. The postal model is one of communication network models. In the postal model, every node should spend α time to set up connection with one of its neighbor node before transmitting message. Moreover, every node can only set up connection with one neighbor node at the same time, but can transmit message to all neighbor nodes that have connection set with simultaneously. The communication network we talk about is a edge- weighted tree, where weight of an edge represents the transmission time (not including the time to set up connection) through this edge. The broadcasting centers are those nodes in the network that initially own the message to be broadcast, the broadcasting problem is to determine the minimum time required and location of broadcasting center such that message is broadcast to all nodes in the network, and the p-center problem is to determine, given the number of broadcasting centers p, the minimum time required and location of the p centers such that message is broadcast to all nodes in the network.
In this thesis, two algorithms are proposed: the first algorithm is to determine, given the time constraint t, the minimum number of broadcasting centers together with their lo- cations such that message is broadcast to all nodes in a given tree network; the second algorithm is to determine, given the number of broadcasting centers p, the minimum time required such that message is broadcast to all nodes in a given tree network. In the first algorithm, we use greedy method and dynamic programming to construct solution of bigger subtree from solutions of smaller subtrees in time complexity O(n2). In the second algorithm, we collect a set of candidates of minimum broadcast time first, then iteratively remove unwanted elements in the set; finally, only the solution would remain. Its time complexity is O(n2 log n). To solve the p-center problem, we use the second algorithm to determine the minimum broadcast time first, then plug the obtained time into the first algorithm as time constraint. Location of the p broadcast centers together with the transmission order of each node would then be determined. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T07:22:14Z (GMT). No. of bitstreams: 1 ntu-107-R06922107-1.pdf: 817677 bytes, checksum: 223f8fdc947becdf33cdb242576ce812 (MD5) Previous issue date: 2018 | en |
dc.description.tableofcontents | 誌謝 i
摘要 ii Abstract iii 1 Introduction 1 1.1 ThePostalModel.............................. 1 1.2 p-CenterProblem.............................. 2 1.3 RelatedWorks................................ 4 2 The Proposed Algorithm I 6 2.1 Notations .................................. 6 2.2 AlgorithmImplementation ......................... 7 2.3 Correctness ................................. 9 2.4 TimeComplexity .............................. 13 3 The Proposed Algorithm II 15 3.1 Notations .................................. 15 3.2 Properties.................................. 16 3.3 AlgorithmImplementation ......................... 18 3.4 Correctness ................................. 19 3.5 TimeComplexity .............................. 20 4 Concluding Remarks 21 4.1 FurtherResearch .............................. 21 Bibliography 24 | |
dc.language.iso | en | |
dc.title | 基於郵政模型在權重樹上的p-廣播中心問題 | zh_TW |
dc.title | Broadcasting p-Centers in a Weighted Tree under the Postal Model | en |
dc.type | Thesis | |
dc.date.schoolyear | 107-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 林清池 | |
dc.contributor.oralexamcommittee | 傅榮勝,張貴雲 | |
dc.subject.keyword | 廣播問題,p-中心,郵政模型,貪進法,動態規劃,二分搜尋法, | zh_TW |
dc.subject.keyword | broadcast problem,p-center,postal model,greedy,dynamic programming,binary search, | en |
dc.relation.page | 26 | |
dc.identifier.doi | 10.6342/NTU201900946 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2019-07-03 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf 目前未授權公開取用 | 798.51 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。