# 臺灣博碩士論文加值系統

(44.220.181.180) 您好！臺灣時間：2024/09/10 05:51

:::

### 詳目顯示

:

• 被引用:0
• 點閱:323
• 評分:
• 下載:23
• 書目收藏:0
 容錯分析一直是研究網路拓樸的重要課題，一般而言我們常使用節點與邊的連接度來衡量一個網路的容錯能力。在本文中，我們將介紹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.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 金字塔網路之漢彌爾頓性質 2 嵌入網狀結構於遞迴環狀圖之研究 3 最佳多容錯環狀與線性陣列網路之建構 4 煎餅圖之結構性質與條件偵錯度研究 5 在一般性弦環圖上找邊互斥展開樹之研究 6 K 元 N 立方體條件連接度之研究 7 連結網路的錯誤分支干擾度研究 8 連結網路上之路徑與迴圏嵌入 9 三種凱利圖上的邊容錯路徑/迴圈嵌入問題之研究 10 條件錯誤下交錯立方體上的容錯問題 11 摺疊式超立方體的容錯研究 12 容錯式煎餅圖中漢米爾頓性質研究 13 蝴蝶圖,遞迴式循環圖及立方體上漢米爾頓容錯性質的研究 14 星狀圖形之容錯廣播演算法

 無相關期刊

 1 諧音字教學法對台灣國小學童英文字彙長期記憶效能之研究 2 國小英語課本之歌曲教材分析 3 具備影像竄改還原或高容忍度之半脆弱影像驗證技巧 4 諧波倍頻磁旋行波放大器 5 服務品質、疏失、補救、顧客滿意之探討－以台南地區量販店為例 6 磁旋返波振盪器之穩定性分析 7 注入式鎖相磁旋返波振盪器之穩定分析 8 探勘正相關及封閉項目集之關聯規則演算法 9 地區醫院策略聯盟與經營績效關係之探討─以某綜合醫院為例─ 10 虛擬學習社群在閱讀學習成效之研究-以苗栗縣福基國小學生網路讀書會為例 11 植基於知識管理流通媒介概念建置校園資訊平台之系統評估－以苗栗縣國小為例 12 大鵬灣國家風景區遊客海域遊憩滿意度之研究 13 在大型交易資料庫中利用有效率演算法探勘關聯規則 14 有效率的從決策表中去除多餘資訊的方法 15 可重覆使用之模糊傳送協定

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