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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳俊樺
研究生(外文):Chun-Hua Chin
論文名稱:在有錯邊的莫氏立方體上的全圓性
論文名稱(外文):Pancyclicity on Mobius Cubes with Maximal Edge Faults
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:27
中文關鍵詞:超立方體圖論連結網路
外文關鍵詞:fault-tolerant embeddingMobius cubesgraph-theoretic interconnection networks
相關次數:
  • 被引用被引用:0
  • 點閱點閱:88
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
  容錯性一直是連結網路中的一個重要課題,主要是討論在圖(graph)中, 若是點與邊發生錯誤,使得網路的失去連通性,在一個圖中,假設其最小長度的圓圈為m, 最大長度的圓圈為n, 若在此圖中存在長度l 的圓圈, m = l = n, 則此圖具有泛圓圈性(pancyclic)的特性。
  在此篇論文中, 我們證明了在n維度的Mobios cubes中, 即使有(n-2)個邊出錯的情況下, Mobios cubes 仍然保有泛圓圈性(pancyclic)的特性。
  A graph G = (V;E) is said to be pancyclic if it contains cycles of all lengths from 4 to |V| in G. Let Fe be the set of faulty edges. In this paper, we show that an n-dimensional Mobius cube, n >= 1, contains a fault-free Hamiltonian path when |Fe| <= (n - 1). We also show that an n-dimensional Mobius cube, n >= 2, is pancyclic when |Fe| <= (n - 2). Since an n-dimensional Mobius cube is regular of degree n, our result achieves optimality in the
worst case.
1 Introduction ....................................3
2 Preliminaries ...................................5
3 A Fault-Free Hamiltonian Path ...................8
4 (N ¡ 2)-Edge-Fault-Tolerant Pancyclic ..........14
5 Concluding Remarks .............................25
[1] S. G. Akl, Parallel Computation: Models and Methods. Prentice Hall, 1997.
[2] N. Ascheuer, Hamiltonian path problems in the on-line optimization of Flexible Manufac-turing Systems, Technical Report TR 96-3, Konrad-Zuse-Zentrumfur Informationstechnik,Berlin, Feb. 1996 (also available at ftp://ftp.zib.de/pub/zib-publications/reports/TR-96-03.PS.Z).
[3] J. C. Bermond, Ed., Interconnection Networks, a special issue of Discrete Applied Mathe-matics, vol. 37+38, 1992.
[4] J. Bruck, R. Cypher, and C. T. Ho, "Fault-tolerant meshes and hypercubes with minimal numbers of spares," IEEE Transaction on Computers, vol. 42, no. 9, pp. 1089{1104, 1993.
[5] J. Bruck, R. Cypher, and C. T. Ho, "Fault-tolerant de Bruijn and shu²e-exchange net-works," IEEE Transaction on Parallel and Distributed Systems, vol. 5, no. 5, pp. 548{553,1994.
[6] J. Bruck, R. Cypher, and C. T. Ho, "On the construction of fault-tolerant cube-connected cycles networks," Journal of Parallel and Distributed Computing, vol. 25, pp. 98{106, 1995.
[7] J. Bruck, R. Cypher, and C. T. Ho, "Wildcard dimensions, coding theory and fault-tolerant meshes and hypercubes," IEEE Transaction on Computers, vol. 44, no. 1, pp. 150{155, 1995.
[8] M. Y. Chan, F. Y. L. Chin, and C. K. Poon, "Optimal simulation of full binary trees on faulty hypercubes," IEEE Transaction on Parallel and Distributed Systems, vol. 6, no. 3, pp. 269{286, 1995.
[9] P. Cull, and S. M. Larson, The MÄobius cubes, in Proceedings of the sixth Distrib. Memory Computing Conference, vol. 44, pp. 699{702, 1991.
[10] K. Diks and A. Pele, "E±cient gossiping by packets in networks with random faults," SIAM Journal on Discrete Mathematics, vol. 9, no. 1, pp. 7{18, 1996.
[11] 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.
[12] F. Harary, Graph theory, Addison-wesley, Massachusetts, 1972.
[13] D. F. Hsu, Interconnection Networks and Algorithms, a special issue of Networks, vol. 23, no. 4, 1993.
[14] W. Huang, Y. Chuang, J. J. M. Tan, L. Hsu, Fault-free Hamiltonian cycle in faulty MÄobius cubes, Computaci¶on y Systemas, vol. 4, no. 2, pp. 106{114, 2000.
[15] A. Kanevsky and C. Feng, On the embedding of cycles in pancake graphs, Parallel Computing, vol. 21, pp. 923{936, 1995.
[16] H. C. Keh and J. C. Lin, On fault-tolerant embedding of Hamiltonian cycles, linear arrays and rings in a Flexible Hypercube", Parallel Computing, vol. 26, pp. 769{781, 2000.
[17] H. K. Ku and J. P. Hayes, "Optimally edge fault-tolerant trees," Networks, vol. 27, pp. 203{214, 1996. 26 BIBLIOGRAPHY 27.
[18] S. Lati‾ and N. Bagherzadeh, "Hamiltonicity of the clustered-star graph with embedding applications," Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1996, pp. 734{744.
[19] A. C. Liang, S. Bhattacharya, and W. T. Tsai, "Fault-tolerant multicasting on hypercubes,"Journal of Parallel and Distributed Computing, vol. 23, pp. 418{428, 1994.
[20] R. S. Lo, and G. H. Chen, Embedding longest fault-free paths in arrangement graphs with faulty vertices, Networks, vol. 37, no. 2, pp. 84{93, 2001.
[21] Y. Rouskov, S. Lati‾, and P. K. Srimani, "Conditional fault diameter of star graph net-works," Journal of Parallel and Distributed Computing, vol. 33, pp. 91{97, 1996.
[22] R. A. Rowley and B. Bose, "Distributed ring embedding in faulty De Bruijn networks,"IEEE Transaction on Computers, vol. 46, no. 2, pp. 187{190, 1997.
[23] H. Sarbazi-Azad, M. Ould-Khaoua, and L. M. Mackenzie, Algorithm construction of Hamil-tonian in pyramids, Information Processing Letters, vol. 80, pp. 75{79, 2001.
[24] Y. C. Tseng, Embedding a ring in a hypercube with both faulty links and faulty nodes,Information Processing Letters, vol. 59, pp. 217{222, 1996.
[25] Y. C. Tseng, S. H. Chang, and J. P. Sheu, Fault-tolerant ring embedding in star graphs with both link and node failures, IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185{1195, 1997.
[26] M. D. Wagh and J. Mo, Hamiltonian cycles in Trivalent Cayley graphs, Information Pro-cessing Letters, vol. 60, pp. 177{181, 1996.
[27] P. J. Yang, S. B. Tien, and C. S. Raghavendra, "Embedding of rings and meshes onto faulty hypercubes using free dimensions," IEEE Transaction on Computers, vol. C-43, no. 5, pp. 608{613, 1994.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 19.林鴻榮(2002)「企業顧客的經營與服務策略─打開企業經營潛在商機之門」,綜效,第156期。頁50-55。
2. 42.邊裕淵(1995)「國際經濟區域化與兩岸經濟關係」,理論與政策,第10卷頁60-72。
3. 54、蔡明田、余明助(2000),「企業文化、組織生涯管理與組織績效之關係研究─以台灣高科技產業為例」,管理評論,第十九卷第三期,PP51-75。
4. 37.葉萬安(1993)「台灣產業政策演變的歷史背景及其效果分析」,行政院經濟建設委員會自由中國之工業,第七十九卷,第四期,頁1-16。
5. 49、賴信榮(1997),「員工激勵誘因」,產業金融季刊,第92期87-88。50、盧瑞陽(1993),「組織行為」,台北:華泰出版。
6. 34.黃鎮台(2001)「兩岸科技產業發展與未來」,國家政策論壇,第1卷5期,頁95-97。
7. 55、蔡秉燁‧鍾靜蓉(2002),「員工生涯規劃」,研習論壇月刊,九十一年三月出版 第十五期。
8. 40、黃英忠、趙必孝(1991),「產業內知覺之新工作比較在離職模式內的因果關係研究」,政治大學管理評論。
9. 26、莊修田(2002),「室內設計業者工作價值關、專業承諾、工作投入與改行傾向關係之研究」,人力資源管理學報,2002夏季號 第二卷 第二期 pp001-018。
10. 32.彭若青(2002)「六個希格瑪的設計幫助企業提升研發能力」,管理雜誌,第337期,頁54-56。
 
系統版面圖檔 系統版面圖檔