(34.239.150.57) 您好!臺灣時間:2021/04/18 23:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊舜光
研究生(外文):Yang, Shun-Kuang
論文名稱:在條件式錯誤分佈情況下之摺疊式超立方體網路拓樸架構上發展可容錯點之迴路嵌入性質
論文名稱(外文):A Study of Vertex-Fault-Tolerant Cycles Embedding in Conditionally Faulty Folded Hypercube Network Topologies
指導教授:郭哲男郭哲男引用關係
指導教授(外文):Kuo, Che-Nan
口試委員:鄭煜輝林鴻南
口試委員(外文):Cheng, Yu-HueiLin, Hung-Nan
口試日期:2018-06-11
學位類別:碩士
校院名稱:稻江科技暨管理學院
系所名稱:動畫遊戲設計學系碩士班
學門:設計學門
學類:綜合設計學類
論文種類:學術論文
論文出版年:2018
畢業學年度:106
語文別:中文
論文頁數:28
中文關鍵詞:互連網路超立方體摺疊式超立方體條件式錯誤迴路
外文關鍵詞:Interconnection networkHypercubeFolded hypercubeConditionally faultyCycle
相關次數:
  • 被引用被引用:0
  • 點閱點閱:35
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
設計互連網路架構是在平行處理和分散式系統中最重要而且不可或缺的部份;其中,迴路是分散式計算中最基本的網路結構,它適合應用於需要較少通訊花費的簡單演算法上面,也適合應用於網路架構上的控制或資料流架構上的分散式計算;許多被設計出為了解決各種代數問題、圖形問題或一些平行應用的高效率演算法,其最初的設計方式都是植基於迴路結構。
當網路中的每一個點至少相鄰g個無錯(fault-free)鄰居時,我們可稱此網路具有條件式錯誤性質(conditionally faulty),其中g>=1。在本論文中,我們定義g-條件式錯誤(g-conditionally faulty)代表網路中的每一個點至少相鄰g個無錯鄰居(neighbors)。接著,我們在4-條件式錯誤情況下的n維摺疊式超立方體上(縮寫為FQ_n)探討各種長度迴路的容錯嵌入性質。首先,令FF_v代表FQ_n中的錯點集合,接著,我們證明出以下兩項性質結果:
性質一:當n>=3且|FF_v|<=2n-5時,FQ_n-FF_v中可嵌入無錯(fault-free)的偶數長度迴路分別為4~2^n-2|FF_v|;
性質二:當n是偶數>=4且|FF_v|<=2n-5時,FQ_n-FF_v中可嵌入無錯的奇數長度迴路分別為n+1~2^n-2|FF_v|-1。
Design of interconnection networks is an important integral part of the parallel processing or distributed system. Cycles, which are one of the most fundamental networks for parallel and distributed computation, are suitable for designing simple algorithms with low communication costs. Cycles can also be used as control/data flow structures for distributed computation in arbitrary networks. Many efficient algorithms were originally designed based on cycles for solving a variety of algebraic problems, graph problems or some parallel applications.
A network is said to be conditionally faulty if its every vertex has at least g fault-free neighbors, where g>=1. In this thesis, we define that a network is g-conditionally faulty if its every vertex has at least g fault-free neighbors. Then, under the 4-conditionally faulty, we consider the fault-tolerant various cycles embedding properties in folded hypercubes FQ_n. Let FF_v denotes the set of faulty vertices in FQ_n. It has been shown the following two properties as that:
Property 1: FQ_n-FF_v contains a fault-free cycle of every even length from 4 to 2^n-2|FF_v| if |FF_v|<=2n-5, where n>=3;
Property 2: FQ_n-FF_v contains a fault-free cycle of every odd length from n+1 to 2^n-2|FF_v|-1 if |FF_v|<=2n-5, where n>=4 and n is even.
中文摘要 ……………………………………………………………………………………………………………i
英文摘要 …………………………………………………………………………………………………………ii
目錄 …………………………………………………………………………………………………………………iii
圖目錄 ………………………………………………………………………………………………………………iv
表目錄 …………………………………………………………………………………………………………………v
第一章 緒論………………………………………………………………………………………………………1
1.1 研究背景與動機……………………………………………………………………………………1
1.2 相關的研究與結果………………………………………………………………………………3
1.3 研究目標…………………………………………………………………………………………………7
1.4 論文架構…………………………………………………………………………………………………7
第二章 圖形理論基礎………………………………………………………………………………8
2.1 基本的定義與名詞……………………………………………………………………………8
2.2 嵌入關係………………………………………………………………………………………………10
第三章 超立方體和摺疊式超立方體之結構與特性……………………13
3.1 超立方體之結構與特性…………………………………………………………………13
3.2 摺疊式超立方體之結構與特性…………………………………………………14
3.3 輔助定理………………………………………………………………………………………………16
第四章 嵌入各種長度迴路於條件式錯誤之FQ_n中……………………19
第五章 結論與未來研究方向…………………………………………………………………23
參考文獻…………………………………………………………………………………………………………24
[1]S. G. Akl, “Parallel computation: models and methods,” Prentice Hall, 1997.
[2]Y. Alavi, J. E. Williamson, “Panconnected graphs,” Studia Scientiarum Mathematicarum Hungarica, vol. 10, no. 1-2, pp. 19-22, 1975.
[3]N. Bagherzadeh, N. Nassif and S. Latifi, “A routing and broadcasting scheme on faulty star graphs,” IEEE Transactions on Computers, vol. 42, no. 11, pp. 1398-1403, 1993.
[4]B. Alspach, D. Hare, “Edge-pancyclic block-intersection graphs,” Discrete Mathematics, vol. 97, no. 1-3, pp. 17-24, 1991.
[5]J. A. Bondy, “Pancyclic graphs,” I. Journal of Combinatorial Theory, vol. 11, pp. 80-84, 1971.
[6]J. M. Chang, J. S. Yang, Y. L. Wang and Y. Cheng, “Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs,” Networks, vol. 44, no.4, pp.302-310, 2004.
[7]D. Cheng, R. X. Hao and Y. Q. Feng, “Cycles embedding on folded hypercubes with faulty nodes,” Discrete Applied Mathematics, vol. 161, pp. 2894-2900, 2013.
[8]D. Cheng, R. X. Hao and Y. Q. Feng, “Odd cycles embedding on folded hypercubes with conditional faulty edges,” Information Sciences, vol. 282, pp. 180-189, 2014.
[9]D. Cheng, R. X. Hao and Y. Q. Feng, “Embedding even cycles on folded hypercubes with conditional faulty edges,” Information Processing Letters, vol. 115, issue. 12, pp. 945-949, 2015.
[10]D. Cheng and D. Guo, “Fault-tolerant cycle embedding in the faulty hypercubes,” Information Sciences, vol. 253, pp. 157-162, 2013.
[11]K. Day and A. E. Al-Ayyoub, “Fault diameter of k-ary n-cube networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 9, pp. 903-907, 1997.
[12]K. Diks and A. Pele, “Efficient gossiping by packets in networks with random faults,” SIAM Journal on Discrete Mathematics, vol. 9, no. 1, pp. 7-18, 1996.
[13]A. H. Esfahanian and S. L. Hakimi, “Fault-tolerant routing in de bruijn communication networks,” IEEE Transactions on Computers, vol. C-34, no. 9, pp. 777-788, 1985.
[14]J. F. Fang, “The bipanconnectivity and m-panconnectivity of the folded hypercube,” Theoretical Computer Science, vol. 385, no. 1-3, pp. 286-300, 2007.
[15]J. S. Fu, “Fault-tolerant cycle embedding in the hypercube,” Parallel computing, vol. 29, no. 6, pp. 821-832, 2003.
[16]J. S. Fu, “Fault-free cycles in folded hypercubes with more faulty elements,” Information Processing Letters, vol. 108, no. 5, pp. 261-263, 2008.
[17]J. S. Fu, “Edge-fault-tolerant vertex-pancyclicity of augmented cubes,” Information Processing Letters, vol. 110, no. 11, pp. 439-443, 2010.
[18]A. Hobbs, “The square of a block is vertex pancyclic,” Journal of Combinatorical Theory, vol. 20, no. 1, pp. 1-4, 1976.
[19]S. Y. 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.
[20]S. Y. Hsieh, “Some edge-fault-tolerant properties of the folded hypercube,” Networks, vol. 51, no. 2, pp. 92-101, 2008.
[21]S. Y. Hsieh and C. N. Kuo, “Hamiltonian-connectivity and strongly hamiltonian-laceability of folded hypercubes,” Computers & Mathematics with Applications, vol. 53, no. 7, pp. 1040-1044, 2007.
[22]S. Y. Hsieh, “A note on cycle embedding in folded hypercubes with faulty elements,” Information Processing Letters, vol. 108, no. 2, pp. 81, 2008.
[23]S. Y. Hsieh, C. N. Kuo and H. H. Chou, “A further result on fault-free cycles in faulty folded hypercubes,” Information Processing Letters, vol. 110, no. 2, pp. 41-43, 2009.
[24]S. Y. Hsieh, C. N. Kuo and H. L. Huang, “1-vertex-fault-tolerant cycles embedding on folded hypercubes,” Discrete Applied Mathematics, vol. 157, issue 14, pp. 3094-3098, 2009.
[25]S. Y. Hsieh and T. J. Lin, “Panconnectivity and edge-pancyclicity of k-ary n-cubes,” Networks, vol. 54, no. 1, pp. 1-11, 2009.
[26]S. Y. Hsieh, T. J. Lin, and H. L. Huang, “Panconnectivity and edge-pancyclicity of 3-ary, N-cubes,” Journal of Supercomputing, vol. 42, pp. 225-233, 2007.
[27]C. N. Kuo and S. Y. Hsieh, “Pancyclicity and bipancyclicity of conditional faulty folded hypercubes,” Information Sciences, vol. 180, issue 15, pp. 2904-2914, 2010.
[28]C. N. Kuo, H. H. Chou, N. W. Chang and S. Y. Hsieh, “Fault- tolerant path embedding in folded hypercubes with both node and edge faults,” Theoretical Computer Science, vol. 475, pp. 82-91, 2013.
[29]C. N. Kuo, C. W. Lee, N. W. Chang and K. H. Shih, “Extended fault-tolerant bipanconnectivity and panconnectivity of folded hypercubes,” International Journal of Mobile Communications, vol. 12, no. 4, pp. 397-410, 2014.
[30]C. N. Kuo, “Every edge lies on cycles embedding in folded hypercubes with vertex-fault-tolerant,” Theoretical Computer Science, vol. 589, pp. 47-52, 2015.
[31]C. N. Kuo, “Pancyclicity and bipancyclicity of folded hypercubes with both vertex and edge faults,” Theoretical Computer Science, vol. 602, pp. 125-131, 2015.
[32]C. N. Kuo, Iain A. Stewart, “Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes,” Theoretical Computer Science, vol. 627, pp. 102-106, 2016.
[33]C. N. Kuo, “Vertex-fault-tolerant cycles embedding in 4-conditionally faulty folded hypercubes,” Discrete Applied Mathematics, vol. 205, pp. 80-85, 2016.
[34]T. L. Kueng, T. Liang, L. H. Hsu and J. M. Tan, “Long paths in hypercubes with conditional node-faults,” Information Sciences, vol. 179, pp. 667-681, 2009.
[35]S. Latifi, “On the fault-diameter of the star graph,” Information Processing Letters, vol. 46, pp.143-150, 1993.
[36]S. Latifi and S. Q. Zheng, “Determination of hamiltonian cycles in cubebased networks using generalized Gray codes,” Journal of Electrical and Computer Engineering, pp. 178-184, 1992.
[37]S. Latifi, S. Q. Zheng and 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.
[38]F. T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays⋅ Trees⋅ Hypercubes, Morgan Kaufman, CA, 1992.
[39]T. K. Li, C. H. Tsai, J. M. Tan and L. H. Hsu, “Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes,” Information Processing Letters, vol. 87, no. 2, pp. 107-110, 2003.
[40]S. C. Liaw, G. J. Chang, F. Cao and D. F. Hsu, “Fault-tolerant routing in circulant networks and cycle prefix networks,” Annals of Combinatorics, vol. 2, pp. 165-172, 1998.
[41]Y. Lu and J. M. Xu, “Panconnectivity of Cartesian product graphs,” Journal of Supercomputing, vol. 56, pp. 182-189, 2011.
[42]M. J. Ma, G. Z. Liu and J. M. Xu, “Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes,” Parallel Computing, vol. 33, no. 1, pp. 36-42, 2007.
[43]M. J. Ma, G. Liu, and X. Pan, “Path embedding in faulty hypercubes,” Applied Mathematics and Computation, vol. 192, pp. 233-238, 2007.
[44]M. J. Ma and J. M. Xu, “Panconnectivity of locally twisted cubes,” Applied Mathematic Letters, vol. 19, no. 7, pp. 681-685, 2006.
[45]J. Mitchem and E. Schmeichel, “Pancyclic and bipancyclic graphs­a survey ,” In: Proc First Colorado Symp on graphs and Applications, Boulder, CO, 1982.
[46]J. H. Park, “Panconnectivity and edge-pancyclicity of faulty recursive circulant G(2m, 4),” Theoretical Computer Science, vol. 390, no. 1, pp. 70-80, 2008.
[47]J. H. Park, H. S. Lim and H. C. Kim, “Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements,” Theortical Computer Science, vol. 377, pp. 170-180, 2007.
[48]Y. Rouskov and P. K. Srimani, “Fault diameter of star graph,” Information Processing Letters, vol. 48, pp. 243-251, 1993.
[49]Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transaction on Computers, vol. 37, pp. 867-872, 1988.
[50]I. A. Stewart and Y. Xiang, “Bipanconnectivity and bipancyclicity in k-ary n-cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 1, pp. 25-33, 2009.
[51]Y. H. Teng, J. M. Tan and L. H. Hsu, “Panpositionable hamiltonicity and panconnectivity of the arrangement graphs,” Applied Mathematics and Computation, vol. 198, no. 1, pp. 414-432, 2008.
[52]C. H. Tsai, J. M. Tan, T. Liang and L. H. Hsu, “Fault-tolerant hamiltonian laceability of hypercubes,” Information Processing Letters, vol. 83, pp. 301-306, 2002.
[53]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.
[54]D. Wang, “Embedding hamiltonian cycles into folded hypercubes with faulty links,” Journal of Parallel and Distributed Computing. vol. 61, pp. 545-564, 2001.
[55]D. B. West, “Introduction to Graph Theory,” Prentice Hall. Upper Saddle River, NJ 07458, 2001.
[56]J. E. Williamson, “Panconnected graphs II,” Periodica Mathematica Hungarica. vol. 8, no. 2, pp. 105-116, 1977.
[57]J. Wu, “Safety levels - an efficient mechanism for achieving reliable broadcasting in hypercubes,” IEEE Transactions on Computers, vol. 44, no. 5, pp. 702-706, 1995.
[58]J. M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht/Bosten/London, 2001.
[59]J. M. Xu and M. Ma, “Survey on path and cycle embedding in some networks,” Frontiers of Mathematics in China, vol. 4, no. 2, pp. 217-252, 2009.
[60]J. M. Xu and M. Ma, “Cycles in folded hypercubes,” Applied Mathematics Letters, vol. 19, pp. 140-145, 2006.
[61]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, 2006.
[62]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.
[63]D. W. Yang and M. M. Gu, “Conditional fault-tolerant edge-bipancyclicity of hypercubes with faulty vertices and edges,” Theoretical Computer Science, vol. 627, pp. 82-89, 2016.
[64]D. W. Yang, Y. Q. Feng, J. H. Kwak and J. X. Zhou, “Fault-tolerant edge-bipancyclicity of faulty hyperucbes under the conditional-fault model,” Information Science, vol. 329, pp. 317-328, 2016.
電子全文 電子全文(網際網路公開日期:20220628)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔