臺灣博碩士論文加值系統

容錯分析一直是研究網路拓樸的重要課題，一般而言我們常使用節點與邊的連接度來衡量一個網路的容錯能力。在本文中，我們將介紹Esfahanian所提出故障禁止集合的概念，並在此假設下重新分析遞迴環狀圖更實際的容錯能力。遞迴環狀圖是由J. H. Park與K. Y. Chwa所提出的一種網路拓樸結構，它是近年來很受重視的一種拓樸結構，因為它擁有許多良好的拓樸性質，例如漢米爾頓迴圈、點對稱、最大點連通與邊連通性、可遞迴建構等等。我們將證明遞迴環狀圖在故障禁止集合的假設下，在c = 1且d = 2時，連接度可達4m - 4﹔在c = 1且d ≠ 2時，連接度可達4m - 2﹔在c = 2時，連接度可達4m﹔在c > 2時，連接度可達4m + 2。

Fault tolerance analysis is very important on interconnection network. In tradition, we use the connectivity of node and edge to measure the fault tolerance capability of interconnection networks. In this paper, we introduce the concept of the forbidden faulty sets that was proposed by Esfahanian. Under the restriction of forbidden faulty sets, we analyze the fault tolerance capability of the recursive circulant graphs. The recursive circulant graph has many good topology properties such as Hamiltonian cycle, node symmetric and can be recursively constructed. Finally, we will prove the connectivity of the recursive circulant with the restriction of forbidden faulty sets. The connectivity can achieve 4m – 4 if c = 1 and d = 2; 4m – 2 if c = 1 and d ≠ 2; 4m if c = 2; 4m + 2 if c > 2.

摘要 iv
英文摘要 v
誌謝 vi
目次 vii
圖目錄 xi
第一章 介紹 1
第二章 遞迴環狀圖的定義與符號 4
第三章 研究結果 7
第四章 結論 9
參考文獻 10

[1]S. B. Akers and B. Krishnamurthy, “The star graph: an attractive alternative to n-cube,” Proceedings of International Conference on Parallel Processing, pp. 393-400, Aug. 1989.
[2]T. Araki and Y. Shibata, “Pancyclicity of recursive circulant graphs,” Information Processing Letters, vol. 81, no. 4, pp. 187-190, 2002.
[3]T. Araki, “Edge-pancyclicity of recursive circulants,” Information Processing Letters, vol. 88, Issue 6, pp. 287-292, December 2003.
[4]D. K. Biss, “Hamiltonian decomposition of recursive circulant graphs,” Discrete Mathematics, vol. 214, Issues 1-3, pp. 89-99, March 2000.
[5]F. Chedid and R. Chedid, “A new variation on hypercubes with smaller diameter,” Information Processing Letters, vol. 46, no. 6, pp. 275-280, July 1993.
[6]W. K. Chen and M. Stallmann, “On embedding binary trees into hypercubes,” Journal of Parallel and Distributed Computing, vol. 24, pp. 132-138, 1995.
[7]K. Efe, “Embedding mesh of trees in the hypercube,” Journal of Parallel and Distributed Computing, vol. 11, no. 3, pp. 222-230, March 1991.
[8]A. El-Amawy, S. Latifi, “Properties and Performance of Folded Hypercubes,” IEEE Transactions on Parallel and Distributed Systems, vol.2, no. 1, pp. 31-42, January 1991.
[9]A. H. Esfahanian, “Generalized measures of fault tolerance with application to n-cube networks,” IEEE Transactions on Computers, vol. 38, no. 11, pp. 1586-1591, November 1989.
[10]G. Fertin and A. Raspaud, “Recognizing Recursive Circulant Graphs,” Electronic Notes in Discrete Mathematics, vol. 5, pp. 112-115, July 2000.
[11]JP Hayes, T. Mudge, QF Stout, S. Colley, and J. Palmer, “A microprocessor-based hypercube supercomputer,” IEEE Micro, vol. 6, pp. 6-17, October 1986.
[12]S. C. Hu and C. B. Yang, “Fault Tolerance on Star Graphs,” International Journal of Foundations of Computer Science, vol. 8, no. 2, pp. 127-142, 1997.
[13]S. Johnsson and C. Ho, “Optimum Broadcasting and Personalized Communication in Hypercubes,” IEEE Transactions on Computers, vol. 38, no. 9, pp. 1249-1268, September 1989.
[14]S. Kim and I. Chung, “Application of the special Latin square to a parallel routing algorithm on a recursive circulant network,” Information Processing Letters, vol. 66, Issue 3, pp. 141-147, May 1998.
[15]E. Leiss and H. Reddy, “Embedding complete binary trees into hypercubes,” Information Processing Letters, vol. 38, pp. 197-199, 1991.
[16]H. S. Lim, J.-H. Park and K. Y. Chwa, “Embedding trees in recursive circulants,” Discrete Applied Mathematics, vol. 69, Issues 1-2, pp. 83-99, August 1996.
[17]C. Micheneau, “Disjoint Hamiltonian cycles in recursive circulant graphs,” Information Processing Letters, vol. 61, Issue 5, pp. 259-264, March 1997.
[18]J. H. Park, K. Y. Chwa, “Recursive circulant: a new topology for multicomputer networks,” Proceeding of International Symposium on Parallel Architectures, pp. 73-80, 1994.
[19]J. H. Park, K. Y. Chwa, “Recursive circulants and their embeddings among hypercubes,” Theoretical Computer Science, vol. 244, no 1-2, pp. 35-62, August 2000.
[20]S. Ponnuswamy and V. Chaudhary, “Analysis of fault tolerance in Cayley digraphs using forbidden faulty sets.” International Conference on Parallel and Distributed Computing and Systems, pp. 346-349, 1994.
[21]Y. Rouskov, S. Latifi, and P. Srimani, "Conditional Fault Diameter of Star Graph Networks," Journal of Parallel and Distributed Computing, vol. 33, pp. 91-97, 1996.
[22]Y. Saad and M. H. Shultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. 37, no. 7, pp. 867-872, Judy 1988.
[23]C. H. Tsai, J. M. Tan and L. H. Hsu, “The super-connected property of recursive circulant graphs,” Information Processing Letters, vol. 91, Issue 6, pp. 293-298, September 2004.
[24]J. Wu and G. Guo, “Fault Tolerance Measures for m-Ary n-Dimensional Hypercubes Based on Forbidden Faulty Sets,” IEEE Transactions on Computers, vol. 47, Issue 8, pp. 888-893, August 1998.
[25]A. Wagner, “Embedding arbitrary binary trees in a hypercube,” Journal of Parallel and Distributed Computing, vol. 7, no. 3, pp. 503–520, 1989.
[26]X. Yang, D. J. Evans and G. M. Megson, “Maximum induced subgraph of a recursive circulant,” Information Processing Letters, vol. 95, Issue 1, pp. 293-298, July 2005.