(3.238.206.122) 您好！臺灣時間：2021/04/21 08:50

### 詳目顯示:::

:

• 被引用: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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 旋轉圖的方散式廣播演算法 2 星狀圖連通網路上尋找點互異的路徑和邊互異的延展樹之演算法

 無相關期刊

 1 應用約略集理論與模糊理論於臺股指數期貨漲跌幅之預測 2 比例式差別服務：比例式過期比率差別服務與封包排程 3 置換性和不可置換性工作之排程 4 符合SCORM標準之概念圖軟體設計與實作 5 組合式基金資金分配策略－蟻元合作系統與遺傳演算法之應用 6 國際股市關聯性結構之研究－Copula模型之應用 7 運用灰預測、灰色馬可夫與適應性模糊類神經推論系統於市場中立型避險基金建構之研究 8 真區段圖中平均編號圖之探討 9 適用於金融機構聯盟共同發行之電子現金 10 具時限性之安全廣播機制 11 雙向旋轉圖上網格圖嵌入之研究 12 網路電話接受度之研究 13 以關聯規則為主的直接行銷演算法 14 行動計算環境中節省能源及降低查詢時間的多目標基因演算法 15 動態洩密者追蹤之金鑰管理機制

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室