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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊昇峰
研究生(外文):Sheng Feng Yang
論文名稱:雙向旋轉圖上獨立展開樹之研究
論文名稱(外文):On the Independent Spanning Trees of Bi-Rotator Graph
指導教授:徐俊傑徐俊傑引用關係
指導教授(外文):Chiun-Chieh Hsu
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:資訊管理系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:57
中文關鍵詞:雙向旋轉圖獨立展開樹演算法容錯廣播
外文關鍵詞:bi-rotator graphindependent spanning trees algorithmfault tolerance broadcasting
相關次數:
  • 被引用被引用:0
  • 點閱點閱:303
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
旋轉圖(bi-rotator graph)最早是由Corbett在1994年所提出的,近幾年來被廣泛的研究。旋轉圖(rotator graph) 經由修改後,將原有的邊由單向改為雙向,因此就成了雙向旋轉圖。誠如星狀圖(star graph)一樣,雙向旋轉圖擁有許多良好的特性,像是點對稱(node symmetry)、較低的直徑(low diameter),以及遞回建構(recursive construction)。
本篇論文主要是在探討如何在任意規模(scale)的雙向旋轉圖下,建構獨立展開樹(independent spanning trees)。在規模為n的雙向旋轉圖中是由n!的點所構成,而且它每個點的分支度(degree)為2n-3。展開樹(spanning trees)它包涵了原圖所有的頂點,且由它所構成的邊是不會有循環的。在一個展開樹中,假如它的任一有向邊均不會與其它展開樹中的邊相同時,我們就可稱這個樹為獨立展開樹。獨立展開樹通常被用來做容錯廣播(fault tolerance broadcasting)。當欲由根節點廣播到其它節點時,每一個獨立展開樹均可充份被利用到,因此,在雙向旋轉圖的容錯廣播,藉由建構這些獨立展開樹即可很容易的實現。
本篇論文,藉著點對稱和遞回建構的特性提供了一個有效率的演算法來建構雙向旋轉圖的獨立展開樹。我們所提出的演算法可建構出2n-3個獨立展開樹座落在n-BR上的一個點,且這個數量已被證明是最大值。
Rotator graphs, first proposed by Corbett in 1994, have been studied in recent years. Later, traditional rotator graphs were modified by adding generation functions to make all edges bi-directional called bi-rotator graphs. Like star graphs, Bi-Rotator graphs also possess rich structure properties, such as symmetry, low diameter and recursive construction.
This thesis focuses on the problems of constructing independent spanning trees for a given scale of the bi-rotator graphs. A bi-rotator graph of scale n contains n! nodes and degree of each node is 2n-3. A spanning tree of a graph is composed of all nodes of the original graph and parts of edges which connect all nodes and form no cycles. Spanning trees are said to be independent if a directed edge can only be consisted in one tree; that is, there exist no common edges in two or more trees. Independent spanning trees are usually utilized in fault-tolerant broadcasting. Each of the independent spanning trees can be applied in a broadcasting process which sends messages from the root to all other nodes through the edges of the tree. Hence, fault tolerance broadcasting in the bi-rotator graph can be achieved by providing multiple independent spanning trees of the graph.
Applying the properties of symmetry and recursive construction, the thesis presents an efficient algorithm of constructing independent spanning trees for a bi-rotator graph. Our algorithm constructs 2n-3 independent spanning trees rooted at a designated node for an n-BR. Hence, the number of the spanning tree is proved to be maximum.
Abstract II
List of figures VI
List of tables VIII
Chapter 1 Introduction 1
1-1. Background and motivation 1
1-2. Outline of the thesis 5
Chapter 2 Preliminaries 7
2-1. Topological properties of the bi-rotator graph 7
2-2. Independent spanning trees 9
2-3. Idea of independent spanning trees construction 11
Chapter 3 Construction of independent spanning trees 13
3-1. Notation and definition 14
3-2. Construction of independent spanning trees algorithm 27
3-3. The upper bound of independent spanning trees’ height 30
3-4. An example of construction of independent spanning
trees 32
3-5. The correctness of our algorithm 52
Chapter 4 Conclusion 54
References 55
[1] 林宏仁,旋轉圖的分散式廣播演算法,國立台灣科技大學資訊管理研究所,民國86年。
[2] 洪明豪,星狀圖連通網路上尋找點互異的路徑和邊互異的延展樹之演算法,私立逢甲大學資訊工程研究所,民國82年。
[3] S. B. Akers and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks”, IEEE Trans. on Computers, vol.38, no.4, pp.555-565, April 1989.
[4] M. Benmaiza and A. Touzene, “One-to-all broadcast algorithm for constant 4 degree cayley graphs”, Parallel Computing, vol.25, pp249-269, 1999.
[5] Ge-Ming Chiu, and Kai-Shung Chen, “Efficient fault-tolerance multicast scheme for hypercube multicomputers”, IEEE Trans. on Parallel and Distributed Systems, vol.9, no.10, pp.952-962, Oct. 1998.
[6] P. F. Corbett, “Rotator graphs: An efficient topology for point-to-point multiprocessor networks”, IEEE Trans. on Parallel and Distributed Systems, vol.3, no.5, pp.622-626, Sept. 1992.
[7] P. Fragopoulou and S. G. Akl, “Edge-disjoint spanning trees on the star network with applications to fault tolerance”, IEEE Trans. on Computers, vol.45, no.2, pp.174-185, Feb. 1996.
[8] H. P. Katseff, “Incomplete hypercubes”, IEEE Trans. on Computers, vol.37, no.5,pp604-607, May 1988.
[9] S. Khuller and B. Schieber, “On independent spanning trees”, Information Processing Letters, vol.42, pp.321-323, 1992.
[10] Y. Lan, “An adaptive fault-tolerance routing algorithm for hypercube multicomputers”, IEEE Trans. on Parallel and Distributed Systems, vol.6, no.11, pp.1147-1152, Nov. 1995.
[11] Hon-Ren Lin and Chiun-Chieh Hsu, “Distributed broadcasting algorithms in rotator graphs”, Communication of IICM, pp.53-66, Dec. 2001.
[12] Hon-Ren Lin and Chiun-Chieh Hsu, “Topological properties of bi-rotator graphs”, IEICE Trans. Inf. & Syst., pp.2172-2178, Vol.E86-D, no10, Oct. 2003.
[13] V. E. Mendia and D. Sarkar, “Optimal broadcasting on the star graph interconnection network”, IEEE Trans. on Parallel and Distributed Systems, vol.3, no.4, pp.389-396, July 1992.
[14] Shin-Hsien Sheu and Chang-Biau Yang, “Multicast algorithms for hypercube multiprocessors”, Journal of Parallel and Distributed Computing, vol. 61, pp.137-149, 2001.
[15] Yu-Chee Tseng and Jang-Ping Sheu, “Toward optimal broadcast in a star graph using multiple spanning trees”, IEEE Trans. on Computers, vol.46, no.5, pp.593-599, 1997.
[16] Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, “Independent spanning trees of chordal rings”, Information Processing Letters, vol.69, pp.155-160, 1994.
[17] Z. Jovanovic and J. Misic, “Fault tolerance of the star graph interconnection network”, Information Processing Letters, vol.49, no.3, pp.145-150, Feb. 1994.
[18] K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi, “Independent spanning trees of product graphs and their construction”, IEICE Trans. Fundamentals, vol.E97-A, no.11, pp.1894-1903, Nov. 1996.
[19] P. Ramanathan and K. G. Shin, “Reliable broadcast in hypercube multicomputers”, IEEE Trans on Computers, vol.46, no.5, pp1654-1657, Dec. 1988.
[20] J. Wu, “Reliable unicasting in faulty hypercubes using safety levels”, IEEE Trans. on Computers, vol.46, no.2, pp.241-247, Feb. 1997.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔