跳到主要內容

臺灣博碩士論文加值系統

(3.81.172.77) 您好!臺灣時間:2022/01/21 19:49
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張定邦
研究生(外文):Ting-Pang Chang
論文名稱:網路上的訊息傳輸問題
論文名稱(外文):Optimal algorithms for dissemination of information
指導教授:張鎮華張鎮華引用關係
指導教授(外文):Gerard J. Chang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:24
中文關鍵詞:傳送聚集散布
外文關鍵詞:broadcastaccumulationgossip
相關次數:
  • 被引用被引用:0
  • 點閱點閱:170
  • 評分評分:
  • 下載下載:25
  • 收藏至我的研究室書目清單書目收藏:0
這篇論文的目的是在研究點不相交或線不相交路徑模式下的連接網路傳輸訊息的問題。在這個傳輸的模式下,一個步驟中一個或二個點經由一條路徑把他們的訊息傳給其他的點。如果有幾個點在點不相交或線不相交的路徑上,則他們可同步傳送。一個演算法的複雜度可用步驟的次數來衡量。
在這篇論文中,我們分別為一點傳送-點不相交模式跟一點傳送-線不相交模式設計線性時間的演算法來解決樹狀圖上的傳送問題。在二點傳送-點不相交的模式下,我們也設計最佳的方法來解決完全k樹狀圖和n維度格子圖上的傳送、聚集、散布問題。

The purpose of this thesis is to investigate the problem of dissemination of information among processors of interconnection networks under the communication mode in which communications are via vertex-disjoint or edge-disjoint paths. In this communication mode, in one communication step, one or two processors send their information to all other processors via a path. Several processors can send information at a same step if the paths used one vertex/edge-disjoint. The complexity of a communication algorithm is measured by the number of communication steps.
In this thesis we design linear-time broadcast algorithms for trees in one-way listen-in vertex-disjoint mode and one-way listen-in edge-disjoint mode. We also design optimal broadcast, accumulation and gossip algorithms for complete k-ary trees and n-dimensional grid in two-way listen-in vertex-disjoint mode.

Abstract (in Chinese) i
Abstract (in English) ii
Contents iii
1. Introduction 1
2. Broadcasting for trees in 1LVDP mode 4
3. Broadcasting for trees in 1LEDP mode 10
4. Complete k-ary trees in 2LVDP mode 16
5. n-Dimensional grid in 2LVDP mode 19
6. Conclusion 23
References 24

H. J. Bockenhauer, Two open problems in communication in edge-disjoint paths modes, Acta Mathematica et Informatica Universitatis Ostraviensis, 7 (1999), 109-117
H. J. Bockenhauer, Communication in the two-way listen vertex-disjoint paths mode, Theoretical Computer Science, 264 (2001), 65-90.
A. M. Farley, Minimum-time line broadcast}, Networks, 10 (1980), 59-70.
R. Feldmann, J. Hromkovic, B. Monien and P. Mysliwietz, Optimal algorithm for dissemination of information in generalized communication modes, Dicrete Applied Mathematics,
53 (1994),55-78.
P. Fraigniaud and E. Lazard, Methods and problems of communication in usual network}, Discrete Applied Mathematics,
53 (1994),79-133.
A. M. Farley, A. Pelc and Proskurowski, Minimum-time multidrop broadcast, Discrete Applied Mathematics, 83 (1998), 61-77.
S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988), 319-349.
J. Hromkovic, R. Klasing, B. Monien and R. Peine, Dissemination of information in interconnection networks (broadcasting and gossiping), Combinatorial Network Theory, 19 (1995), 125-212.
J. Hromkovic, R. Klashing and E. A. Stohr, Dissemination of information in vertex-disjoint paths mode I, Computers and Artificial Intelligence, 15 (1996), 295-318.
J. Hromkovic, R. Klashing, E. A. Stohr and H. Wagener, gossiping in vertex-disjoint paths mode, Information and Computation, 123 (1995), 17-28.
J. Hromkovic, R. Klashing, W. Unger and H. Wagener, Optimal algorithms for broadcast and gossip in the edge-disjoint path modes}, Information and Computation, 133 (1997), 1-33.
J. Hromkovic, K. Lorys, P. Kanarek, R. Klashint, W. Unger and H. Wagener, On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks}, Proc. of the 12th Symposium on Theoretical Aspects ofComputer Science (STACS'95), Springer LNCS 900, 255-266.
R. Klasing, On the complexity of broadcast and gossip in different communication modes}, Shaker Verlag, Aachen, 1996.
R. Klasing, The relationship between gossiping in vertex-disjoint paths mode and bisection width}, Discrete Applied Mathematics, 82 (1998), 227-244.
P. J. Slater, E. J. Cockayne and S. T. Hedetniemi, information dissemination in trees}, SIAM J. Computing, 10 (1981), 692-701.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top