請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/71276完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
| dc.contributor.author | Zih-Wei Huang | en |
| dc.contributor.author | 黃子瑋 | zh_TW |
| dc.date.accessioned | 2021-06-17T05:02:22Z | - |
| dc.date.available | 2018-08-01 | |
| dc.date.copyright | 2018-08-01 | |
| dc.date.issued | 2018 | |
| dc.date.submitted | 2018-07-24 | |
| dc.identifier.citation | [1] P. J. Slater, E. J. Cockayne, and S. T. Hedetneniemi, “Informatiom of dissem- ination in trees,” SIAM Journal on Computing, vol. 10, no. 4, pp. 692–701, 1981.
[2] A. Jakoby, R. Reischuk, and C. Shindelhauer, “The complexity of broad- casting in planar and decomposable graphs,” Discrete Applied Mathematics, vol. 83, pp. 179–206, 1998. [3] G. Kortsarz and D. Peleg, “Approximation algorithms for minimum time broadcast,” SIAM Journal on Discrete Mathematics, vol. 8, pp. 401–427, 1995. [4] M. Elkin and G. Kortsarz, “Sublogarithmic approximation for telephone mul-ticast,” Journal of Computerand System Sciences,vol.72,pp.648–659,2006. [5] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, “Multicasting in heteroge- neousnetwork,” Proceedings of the 13th ACM Symposiumon Theory of Computing, pp. 448–453, 1998. [6] H. A. Harutyunyan and B. Shao, “An efficient heuristic for broadcasting in networks,” Journal of Parallel and Distributed Computing, vol. 66, pp. 68– 76, 2006. [7] R. Beier and J. F. Sibeyn, “A powerful heuristic for telephone gossiping,” Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity, pp. 17–36, 2000. [8] P. Scheuermann and G. Wu, “Heuristic algorithms for broadcasting in point- to-point computer networks,” IEEE Transactions on Computers, vol. C-33, pp. 804–811, 1984. [9] H. A. Harutyunyan and E. Maraachlian, “On broadcasting in unicyclic graphs,” Journal of Combinatorial Optimization, vol. 16, no.3, pp. 307–322, 2008. [10] H. A. Harutyunyan and E. Maraachlian, “Broadcasting in fully connected trees,” Proceedings of the IEEE International Conference on Parallel and Distributed Systems, pp. 740–745, 2009. [11] P.BhabakandH.A.Harutyunyan,“Broadcastprobleminhypercubeoftrees,”Frontiers in Algorithmics, pp. 1–12, 2014. [12] H. A. Harutyunyan, G. Laza, and E. Maraachlian, “Broadcasting in necklace graphs,” Proceedings of the Canadian Conference on Computer Science and Software Engineering, vol. 2, pp. 253–256, 2009. [13] E. Maraachlian, “Optimal broadcasting in tree-like graphs,” Ph.D. Thesis of Concordia University, 2010. [14] J. M. Koh and D. W. Tcha, “Information dissemination in trees with nonuni- form edge transmission times,” IEEE Transactions on Computers, vol.40, no. 10, pp. 1174–1177, 1991. [15] Y. H. Su, C. C. Lin, and D. T. Lee, “Broadcasting in weighted trees under the postal model,” Theoretical Computer Science, vol. 621, pp. 73–81, 2016. [16] C. H. Tsou, G. H. Chen, H. I. Yu, and C. C. Lin, “The broadcast median prob- lem in heterogeneous postal model,” Journal of Combinatorial Optimization, vol. 25, no. 4, pp. 602–616, 2013. [17] H. W. Kuhn, “The hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, pp. 83–97, 1955. [18] A. Tamir, “An O(pn2) algorithm for the p-median and related problems on tree graphs,” Operations Research Letters, vol. 19, no. 2, pp. 59–64, 1996. [19] 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. [20] A. Farley and A. Proskurowski, “Broadcasting in trees with multiple originators,” Journal of Parallel and Distributed Computing, vol. 2, no. 4, p. 381– 386, 2006. [21] N.Blum,“A simplified realization of the hopcroft-karp approach to maximum matching in general graphs,” Tech. Rep., University of Bonn, 2001. [22] E. Minieka, “The delivery man problem on a tree network,” Annals of Operations Research, vol. 18, p. 261–266, 1989. [23] R. Sitters, “The minimum latency problem is np-hard for weighted trees,”Proceedings of IPCO, pp. 230–239, 2002. [24] I. Averbakh and O. Berman, “Sales-delivery man problems on treelike networks,” Networks, vol. 25, pp. 45–58, 1995. [25] M. R. Garey and D. S. Johnson, “Complexity results for multiprocessor scheduling under resource constraints,” SIAM Journal on Computing, vol. 4, no. 4, pp. 397–411, 1974. [26] J. E. Hopcroft and R. M. Karp, “An n^5/2 algorithm for maximum matchings in bipartite graphs,” SIAM Journal on Computing, vol. 2, no. 4, p. 225–231, 1973. [27] H. W. Kuhn, “Variants of the hungarian method for assignment problems,”Naval Research Logistics Quarterly, vol. 3, pp. 253–258, 1956. [28] J. Munkres, “Algorithms for the assignment and transportation problems,” Journal of the Society for Industrial and Applied Mathematics, vol. 5, no. 1, pp. 32–38, 1957. [29] S. Arora, “Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems,” Journal of the ACM, vol. 45, no. 5, pp. 753–782, 1998. [30] J. Beardwood, J. H. Halton, and J. M. Hammersley,“The shortest path through many points,” Proceedings of the Cambridge Philosophical Society, pp. 299– 327, 1959. [31] C. H. Papadimitriou, “The euclidean traveling salesman problem is np-complete,” Theoretical Computer Science, vol. 4, no. 3, pp. 237–244, 1977. [32] C. H. Papadimitriou and M. Yannakakis, “The traveling salesman problem with distances one and two,” Mathematics of Operations Research, vol. 18, pp. 1–11, 1993. [33] S.Steinerberger,“New bounds for the traveling salesman constant,” Advances in Applied Probability, p. 47, 2015. [34] W. Cook, D. Espinoza, and M. Goycoolea, “Computing with domino-parity inequalities for the tsp,” INFORMS Journal on Computing, vol. 19, no. 3, pp. 356–365, 2007. [35] V. Poirriez, N. Yanev, and R. Andonov, “A hybrid algorithm for the un- bounded knapsack problem,” Discrete Optimization, vol. 6, no. 1, pp. 110– 124, 2009. [36] R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem : dynamic programming revisited,” European Journal of Operational Research, vol. 123 no. 2, pp. 168–181, 2000. [37] J. S. B. Mitchell, “Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems,” SIAM Journal on Computing, vol. 28, no. 4, pp. 1298–1309, 1999. [38] D. J. Rosenkrantz, R. E. Stearns, and P. Lewis, “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal on Computing, vol. 6, no. 5, p. 563–581, 1977. [39] S. Martello, D. Pisinger, and P. Toth, “Dynamic programming and strong bounds for the 0-1 knapsack problem,” Management Science, vol. 45, p. 414– 424, 1999. [40] G. Plateau and M. Elkihel, “A hybrid algorithm for the 0-1 knapsack problem,” Mathematical Methods of Operations Research, vol. 49, pp. 277–293, 1985. [41] E. Horowitz and S. Sahni, “Computing partitions with applications to the knapsack problem,” Journal of the ACM, vol. 21, pp. 277–292, 1974. [42] S. A. Cook, “The complexity of theorem-proving procedures,” Proceedings of the 3th Annual ACM Symposium on Theory of Computing, p. 151–158, 1971. [43] U. Schöning, “A probabilistic algorithm for k-sat and constraint satisfaction problems,” Proceedings of the 40th Annual Symposium Foundations of Com- puter Science, pp. 410–414, 1999. [44] T. J. Schaefer, “The complexity of satisfiability problems,” Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216–226, 1978. [45] V.Kann,“Maximum bounded 3-dimensional matching is max snp-complete,”Information Processing Letters, vol. 37, no. 1, pp. 27–35, 1991. [46] M. Karpinski, A. Rucinski, and E. Szymanska, “The complexity of perfect matching problems on dense hypergraphs,” Proceedings of the International Symposium on Algorithms, vol. 20, pp. 626–636, 2009. [47] R. M. Karp, “Reducibility among combinatorial problems,” Complexity of Computer Computations, pp. 85–103, 1972. [48] P. Keevash, F. Knox, and R. Mycroft, “Polynomial-time perfect matchings in dense hypergraphs,” Proceedings of the 45th annual ACM symposium, pp. 311–320, 2013. [49] D. Pisinger, “Linear time algorithms for knapsack problems with bounded weights,” Journal of Algorithms, vol. 33, pp. 1–14, 1999. [50] A. Schrijver, “On the history of the transportation and maximum flow problems,” Mathematical Programming, vol. 91, no. 3, pp. 437–445, 2002. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/71276 | - |
| dc.description.abstract | 本論文提出一個演算法來解決在郵政模型中的權重樹上找出一個具時間限制的廣播中心問題。給定一權重樹 T = (V,E) 及時間限制 t ，在郵政模型的規則下傳播，邊的權重在此用來表示相鄰兩點間傳送資訊所需的時間，時間限制 t 指的是所有點接受到訊息的時間不能超出 t 。在此論文中我們希望能夠找出一個最佳的廣播中心，使得廣播訊息給樹中所有點所花費的時間總和最小，且所有的點都能在時間 t 內接收到訊息，同時我們的演算法也會得到整顆樹的最佳廣播時間，以及最佳的廣播順序。在這篇論文中我們結合了動態規劃法還有匈牙利演算法，提出一個 O(min(t,n) · n4) 時間複雜度的演算法來解決這個問題。 | zh_TW |
| dc.description.abstract | We propose the problem of finding a broadcast median on a weighted tree with time con- straint under the postal model. Given a weighted tree T = (V,E) with time constraint t, the overall delay of a vertex v ∈ V (T ), is the minimum sum of the transmission time required to send a message from v to all vertices in T , and the medain is the node that has the minimum overall delay. Time constraint t denotes that all nodes in T should receive the message before time t.In this thesis, weproposean O(min(t,n)·n4) time complexity algorithm that uses dynamic programming and Hungarian Algorithm to find a median in T with time constraint. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T05:02:22Z (GMT). No. of bitstreams: 1 ntu-107-R05922156-1.pdf: 884350 bytes, checksum: 7c198c40e41b469b00003bac6792c8bd (MD5) Previous issue date: 2018 | en |
| dc.description.tableofcontents | 誌謝i
摘要ii Abstract iii 1 Introduction 1 1.1 Non-uniform postal model . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Outline of the thesis and contribution . . . . . . . . . . . . . . . . . . . . 4 2 A Dynamic Programming Algorithm 6 2.1 Notations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Algorithm implementation . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Correctness and Time Complexity of the Algorithm 14 3.1 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Time complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4 Conclusion 19 Bibliography 21 | |
| 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 | 權重樹 | zh_TW |
| dc.subject | time constraint | en |
| dc.subject | dynamic programming | en |
| dc.subject | weighted tree | en |
| dc.subject | postal model | en |
| dc.subject | broadcasting problem | en |
| dc.subject | broadcast median | en |
| dc.title | 在權重樹上尋找具時間限制的廣播中心問題 | zh_TW |
| dc.title | Finding a Broadcast Median with Time Constraint on a
Weighted Tree | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 106-2 | |
| 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 | broadcasting problem,broadcast median,time constraint,dynamic programming,weighted tree,postal model, | en |
| dc.relation.page | 27 | |
| dc.identifier.doi | 10.6342/NTU201801275 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2018-07-25 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-107-1.pdf 未授權公開取用 | 863.62 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。