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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張碩峰
研究生(外文):Shuo-Feng Chang
論文名稱:植基於摺疊式超立方體網路拓樸架構上探討可容錯一點之雙分泛連結與泛連結性質
論文名稱(外文):1-Vertex-Fault-Tolerant Bipanconnectivity and Panconnectivity of Folded Hypercubes Network Topology
指導教授:郭哲男郭哲男引用關係
指導教授(外文):Dr. Che-Nan Kuo
口試委員:林鴻南林聰結
口試日期:2013-06-17
學位類別:碩士
校院名稱:稻江科技暨管理學院
系所名稱:數位內容設計與管理學系研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:37
中文關鍵詞:超立方體摺疊式超立方體互連網路雙分圖形無錯容錯嵌入泛連結雙分泛連結
外文關鍵詞:HypercubeFolded hypercubeInterconnection networksBipartite graphFault-freeFault-tolerant embeddingPanconnectivityBipanconnectivity
相關次數:
  • 被引用被引用:0
  • 點閱點閱:115
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本篇論文中,我們分析了一種超立方體(hypercube)網路拓樸的變形架構,稱作為摺疊式超立方體(folded hypercube,縮寫為 ),它是標準的超立方體網路拓樸再加上一些額外的邊所構成的架構。
首先,在n維的摺疊式超立方體 中,令x和y為兩個相異且無錯(fault-free)的點,而f代表一個錯點,接著,我們將探討兩個結果,它們分別代表了 中擁有雙分泛連結以及 -泛連結的性質,分述如下:
性質一(雙分泛連結性質):當 時, 中任意兩個點x和y之間均存在可容錯的路徑長度l為 ,其中 且 代表x和y在 中的最短路徑。
性質二( -泛連結性質):當n是偶數且 2的情況下, 中任意兩個點x和y之間均存在可容錯的路徑長度l為 。
根據以上兩項結果得知, 中所嵌入的各種不同長度路徑是在最差狀況(worst case)下的最理想結果。

In this thesis, we analysis a hypercube variant structure, the folded hypercube, which is basically a standard hypercube with some extra links between its nodes.
Let x and y be any two distinct fault-free vertices, f be a faulty vertex in an n-dimensional folded hypercube . Then, we show the following two results which respective obtain the bipanconnected and the -panconnected properties of , as follows:
Property 1(Bipanconnectivity):If , contains a fault-free x-y path of every length l such that and , where denotes the distance between x and y in .
Property 2( -panconnectivity):If is even, contains a fault-free x-y path of every length l such that .
According to the above two results, we know that the lengths of fault-free paths obtained of are worst case optimal.

中文摘要 ……………………………………………………………………………i
英文摘要 ...….….…………………………………………………….…………….ii
誌 謝 ..….….…………………………………………………….…………….iii
目錄 ………………………………………………………………………......iv
圖目錄 ……………………………………………………………………….......v
表目錄 ………………………………………………………………………......vi
第一章 緒論…………………………………………………………………........1
1.1 研究背景與動機………………………………………………………….1
1.2 相關的研究與結果……………………………………………………….2
1.3 研究目標………………………………………………………………….5
1.4 論文架構………………………………………………………………….6
第二章 圖形理論基礎……………………………………………………………7
2.1 基本的定義與名詞……………………………………………………….7
2.2 嵌入關係………………………………………………………………….9
第三章 超立方體和摺疊式超立方體之結構與特性………………………..…12
3.1 超立方體之結構與特性……………………..………………………….12
3.2 摺疊式超立方體之結構與特性………………..……………………….13
3.3 輔助定理………………………………………………………………...15
第四章 中的雙分泛連結與 -泛連結性質嵌入……………………...19
第五章 結論與未來研究方向…………………………………………………..26
參考文獻…………………………………………………... ………………………27

[1] Y. Alavi, J. E. Williamson, “Panconnected graphs,” Studia Scientiarum Mathematicarum Hungarica, vol. 10, no. 1-2, pp. 19-22, 1975.
[2] B. Alspach, D. Hare, “Edge-pancyclic block-intersection graphs,” Discrete Mathematics, vol. 97, no. 1-3, pp. 17-24, 1991.
[3] J. A. Bondy, “Pancyclic graphs,” I. Journal of Combinatorial Theory, vol. 11, pp. 80-84, 1971.
[4] Xie-Bin Chen, “Some results on topological properties of folded hypercubes,” Information Processing Letters, vol. 109, pp. 395-399, 2009.
[5] J. -F. Fang, “The bipanconnectivity and m-panconnectivity of the folded hypercube,” Theoretical Computer Science, vol. 385, no. 1-3, pp. 286-300, 2007.
[6] J. -S. Fu, “Fault-tolerant cycle embedding in the hypercube”, Parallel computing, vol. 29, no. 6, pp. 821-832, 2003.
[7] J. -S. Fu, “Fault-free cycles in folded hypercubes with more faulty elements,” Information Processing Letters, vol. 108, no. 5, pp.261-263, 2008.
[8] J. -S. Fu, “Fault-free cycles in folded hypercubes with more faulty elements,” Information Processing Letters, vol. 108, no. 5, pp.261-263, 2008.
[9] A. Hobbs, “The square of a block is vertex pancyclic”, Journal of Combinatorical Theory, vol. 20, no. 1, pp. 1-4, 1976.
[10] Sun-Yuan Hsieh, “Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges”, Parallel Computing, vol. 32, no. 1, pp. 84-91, 2006.
[11] Sun-Yuan Hsieh, “Some edge-fault-tolerant properties of the folded hypercube,” Networks, vol. 51, no. 2, pp. 92-101, 2008.
[12] Sun-Yuan Hsieh and Che-Nan Kuo, “Hamilton-connectivity and strongly Hamiltonian -laceability of folded hypercubes,” Computers & Mathematics with Applications, vol. 53, no. 7, pp. 1040-1044, 2007.
[13] Sun-Yuan Hsieh, “A note on cycle embedding in folded hypercubes with faulty elements,” Information Processing Letters, vol. 108, no. 2, pp. 81, 2008.
[14] Sun-Yuan Hsieh, Che-Nan Kuo and Hsin- Hung Chou, “A further result on fault-free cycles in faulty folded hypercubes,” Information Processing Letters, vol. 110, no. 2, pp. 41-43, 2009.
[15] Sun-Yuan Hsieh, Che-Nan Kuo and Hui- Ling Huang, “1-Vertex- Fault-Tolerant Cycles Embedding on Folded Hypercubes,” Discrete Applied Mathematics, vol. 157, issue 14, pp. 3094-3098, 2009.
[16] Che-Nan Kuo and Sun-Yuan Hsieh, “Pancyclicity and Bipancyclicity of Conditional Faulty Folded Hypercubes,” Information Sciences, vol. 180, issue 15, pp. 2904-2914, 2010.
[17] Che-Nan Kuo, Hsin- Hung Chou, Nai-Wen Chang, and Sun-Yuan Hsieh, “Fault-Tolerant Path Embedding in Folded Hypercubes with Both Node and Edge Faults,” Theoretical Computer Science, vol. 475, pp. 82-91, 2013.
[18] S. Latifi, S. -Q. Zheng, “Determination of hamiltonian cycles in cubebased networks using generalized Gray codes,” Journal of Electrical and Computer Engineering, pp. 178-184, 1992.
[19] S. Latifi, S. Q. Zheng, N. Bagherzadeh, “Optimal ring embedding in hypercubes with faulty links,” Proceedings of the IEEE Symposium on Fault-Tolerant Computing, vol. 21, no. 3 , pp. 189-199, 1995.
[20] F. T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays⋅ Trees⋅ Hypercubes, Morgan Kaufman, CA, 1992.
[21] T. K. Li, C. H. Tsai, J. M. Tan, L. H. Hsu, “Bipannectivity and edge-fault-tolerant bipancyclicity of hypercubes,” Information Processing Letters, vol. 87, no. 2, pp. 107-110, 2003.
[22] J. Mitchem, E. Schmeichel, “Pancyclic and bipancyclic graphs­a survey ,” In: Proc First Colorado Symp on graphs and Applications, Boulder, CO, 1982.
[23] C. -H. Tsai, J. -M. Tan, T. Liang, L.-H. Hsu, “Fault-tolerant Hamiltonian laceability of hypercubes,” Information Processing Letters, vol. 83, 301-306, 2002.
[24] C. -H. Tsai, “Linear array and ring embedding in conditional faulty hypercubes,” Theoretical Computer Science, vol. 314, 431-443, 2004.
[25] Y. -C. Tseng, “Embedding a ring in a hypercube with both faulty links and faulty nodes,” Information Processing Letters, vol. 59, no. 4, pp. 217-222, 1996.
[26] D. Wang, “Embedding Hamiltonian cycles into folded hypercubes with faulty links,” Journal of Parallel and Distributed Computing. vol. 61, pp. 545-564, 2001.
[27] D. B. West, “Introduction to Graph Theory,” Prentice Hall. Upper Saddle River, NJ 07458, 2001.
[28] J. E. Williamson, “Panconnected graphs II,” Periodica Mathematica Hungarica. vol. 8, no. 2, pp. 105-116, 1977.
[29] J. -M. Xu and M. Ma, “Cycles in folded hypercubes,” Applied Mathematics Letters, vol. 19, pp. 140-145, 2006.
[30] J. -M. Xu, M. J. Ma, and Z. Z. Du, “Edge-fault-tolerant hamiltonicity of folded hypercubes,” Journal of University of Science and Technology of China, vol. 36, no. 3, pp. 244-248, 2007.
[31] J. -M. Xu, M. J. Ma, and Z. Z. Du, “Edge-fault-tolerant properties of hypercubes and folded hypercubes,” Australasian Journal of Combinatorics, vol. 35, pp. 7-16, 2006.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔