跳到主要內容

臺灣博碩士論文加值系統

(35.172.136.29) 您好!臺灣時間:2021/07/29 08:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃煜翔
研究生(外文):Yu-Shiang Huang
論文名稱:具時間限制的廣播中心問題
論文名稱(外文):Broadcast Centers in Trees with Time Constraints
指導教授:陳健輝陳健輝引用關係
指導教授(外文):Gen-Huey Chen
口試委員:胡家正周信宏
口試委員(外文):Chia-Cheng HuHsin-Hung Chou
口試日期:2015-06-23
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:52
中文關鍵詞:廣播中心點問題時間限制異質郵寄模型樹狀結構貪進法
外文關鍵詞:broadcast center problemtime constraintheterogeneous postal modeltreesgreedy method
相關次數:
  • 被引用被引用:0
  • 點閱點閱:115
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文提出一 O(n) 時間複雜度的演算法來解決樹狀結構上的廣播中心點問題,使廣播中心點的數量最少。廣播按照異質郵寄模型的規則進行,需在時間限制內完成。

In this thesis, we present a O(n)-time exact algorithm to find a broadcast strategy such that broadcasting can be completed within the time constraint and the number of centers is minimal. The given graph is a tree and broadcasting is under the heterogeneous postal model.

口試委員會審定書 iii
誌謝 v
Acknowledgements vii
摘要 ix
Abstract xi
1 Introduction 1
1.1 Broadcast Problem and Models . . . . . . . . . . . . . 1
1.2 Main Results and Thesis Organization . . . . . . . . . 2
2 Preliminaries 3
2.1 Notations and Definitions . . . . . . . . . . . . . . . . 3
2.2 Related Works . . . . . . . . . . . . . . . . . . . . . . 5
3 A Linear-Time Algorithm 7
3.1 Algorithm Description . . . . . . . . . . . . . . . . . . 7
3.2 Finding SUCC(v) and b_time(v) . . . . . . . . . . . . 9
3.3 Evaluatng spare(v) . . . . . . . . . . . . . . . . . . . . 11
xiii
3.4 A Non-Sorting Method . . . . . . . . . . . . . . . . . . 12
3.5 Time Complexity . . . . . . . . . . . . . . . . . . . . . 16
4 Correctness 19
4.1 Minimum Unused Edges and Broadcast Time . . . . . 20
4.2 Earliest Spare Time . . . . . . . . . . . . . . . . . . . 23
4.3 Correctness of the Algorithm . . . . . . . . . . . . . . 24
5 Two Illustrative Examples 29
5.1 The First Example . . . . . . . . . . . . . . . . . . . . 29
5.2 The Second Example . . . . . . . . . . . . . . . . . . . 39
6 Conclusion 47
Bibliography 49

[1] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, “Message multicasting in heterogeneous networks,” SIAM Journal on Computing, vol.
30, no. 2, pp. 347–358, 2000.
[2] A. Bar-Noy and S. Kipnis, “Designing broadcasting algorithms in the
postal model for message-passing systems,” Mathematical Systems
Theory, vol. 27, no. 5, pp. 431–452, 1994.
[3] A. Bar-Noy and S. Kipnis, “Multiple message broadcasting in the
postal model,” Networks, vol. 29, no. 1, pp. 1–10, 1997.
[4] J.-m. Koh and D.-w. Tcha, “Information dissemination in trees with
nonuniform edge transmission times,” IEEE Transactions on Computers, vol. 40, no. 10, pp. 1174–1177, 1991.
[5] P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi, “Information dissemination in trees,” SIAM Journal on Computing, vol. 10, no. 4,
pp. 692–701, 1981.
[6] R. Ravi, “Rapid rumor ramification: approximating the minimum broadcast time,” in Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 202–213.
[7] G. Kortsarz and D. Peleg, “Approximation algorithms for minimumtime broadcast,” SIAM Journal on Discrete Mathematics, vol. 8, no.
3, pp. 401–427, 1995.
49
[8] 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, 2003, pp. 76–
85.
[9] R. Beier and J. F. Sibeyn, A Powerful Heuristic for Telephone Gossiping. Citeseer, 2000.
[10] 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.
[11] P. Scheuermann and G. Wu, “Heuristic algorithms for broadcasting
in point-to-point computer networks,” IEEE Transactions on Computers, vol. 100, no. 9, pp. 804–811, 1984.
[12] H. A. Harutyunyan and E. Maraachlian, “On broadcasting in unicyclic graphs,” Journal of Combinatorial Optimization, vol. 16, no.
3, pp. 307–322, 2008.
[13] 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, 2009, pp. 253–256.
[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, 2009, pp. 740–745.
[15] P. Bhabak and H. A. Harutyunyan, “Broadcast problem in hypercube
of trees,” Lecture Notes in Computer Science : Frontiers in Algorithmics, vol. 8497, pp. 1–12, 2014.
[16] E. Maraachlian, “Optimal broadcasting in treelike graphs,” PhD thesis, Concordia University, 2010.
50
[17] Y.-H. Su, C.-C. Lin, and D. T. Lee, “Broadcasting in heterogeneous
tree networks,” Lecture Notes in Computer Science : Computing and
Combinatorics, vol. 6196, pp. 368–377, 2010.
[18] A. Farley, S. Hedetniemi, S. Mitchell, and A. Proskurowski, “Minimum
broadcast graphs,” Discrete Mathematics, vol. 25, no. 2, pp. 189–193,
1979.
[19] A. M. Farley, “Broadcast time in communication networks,” SIAM
Journal on Applied Mathematics, vol. 39, no. 2, pp. 385–390, 1980.
[20] 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.
[21] 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.
[22] 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.
[23] P. Fraigniaud and E. Lazard, “Methods and problems of communication in usual networks,” Discrete Applied Mathematics, vol. 53, no.
1, pp. 79–133, 1994.
[24] H. Grigoryan, “Problems related to broadcasting in graphs,” PhD thesis, Concordia University, 2013.
[25] 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.
51
[26] J. Hromkovič, R. Klasing, B. Monien, and R. Peine, “Dissemination
of information in interconnection networks (broadcasting & gossiping),” Combinatorial Network Theory, pp. 125–212, 1996.
[27] 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.
[28] 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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文