跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:歐宗翰
研究生(外文):Tsung-Han Ou
論文名稱:星狀圖的漢米爾頓可蕾絲相鄰點容錯之研究
論文名稱(外文):The Study of Adjacent Vertices Fault Tolerance Hamiltonian Laceability of Star Graphs
指導教授:洪春男
指導教授(外文):Chun-Nan Hung
口試委員:洪春男徐力行黃鈴玲
口試委員(外文):Chun-Nan HungLih-Hsing HsuLing-Ling Huang
口試日期:2012-06-27
學位類別:碩士
校院名稱:大葉大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:38
中文關鍵詞:星狀圖相鄰點容錯邊容錯
外文關鍵詞:star graphadjacent vertices fault toleranceedges fault tolerance
相關次數:
  • 被引用被引用:0
  • 點閱點閱:127
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  在連結網路中Star graph是一個耳熟能詳的拓樸網路架構。此論文中探討星狀圖的一些漢米爾頓特性之邊容錯和相鄰點容錯。
  先令Sn 為一個n 維的星狀圖,再令Fe是Sn上壞邊的集合和Fav 是Sn 上壞相鄰對點的集合。在這篇論文中,我們要建構一個當b 和w 為任意兩個奇數長度的點並且 fav + fe ≤ 3 及n ≥ 5,在Sn – Fav – Fe 時還存在一條漢米爾頓路徑 P(b, w) 的星狀圖。

  The star graph is a famous interconnection network. In this thesis, we will investigate the edge fault tolerance and adjacent vertex fault tolerance for some Hamiltonian property of the star graph.
  Let Sn be an n-dimensional star graph, and let Fe be the set of fe faulty edges and let Fav be the set of fav pairs of adjacent faulty vertices of Sn. In this thesis, we show that there exists a Hamiltonian path P(b, w) of Sn –Fav – Fe where b and w are arbitrary two vertices with odd distance for fav + fe ≤ n - 3and n ≥ 5.

封面內頁
簽名頁
中文摘要
ABSTRACT
誌謝
目錄
圖目錄

Chapter1 Introduction1
Chapter2 Preliminaries
2.1 Previous results
2.2 Some additional lemmas
Chapter3 The Main Result
Chapert4 Conclusion

[1] S.B. Akers, B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks,” IEEE Transaction on Computers, 38, pp. 555-566, 1989.
[2] N. Bagherzadeh, M. Dowd, N. Nassif, “Embedding an arbitrary binary tree into the star graph,” IEEE Trans. Comput., pp. 475-481, 1996.
[3] J.H. Chang, C.S. Shin, K.Y. Chwa, “Ring embedding in faulty star graphs,” IEICE Trans. Fund. E82-A. pp. 1953-1964, 1999.
[4] C. Dongqin, G. Dachang, “Cycle embedding in star graphs with more conditional faulty edges,” Applied Mathematics and Computation, 218, pp. 3856-3867, 2011.
[5] T. Dvoˇr´ak, “Hamiltonian cycles with prescribed edges in hypercubes,” SIAM J. Discrete Math. 19 (2005) 135-144.
[6] T. Dvoˇr´ak, P. Gregor, “Hamiltonian paths with prescribed edges in hypercubes,” Discrete Mathematics 307 (2007) 1982-1998.
[7] J.S. Fu, “Conditional fault-tolerant hamiltonicity of star graphs,” Parallel Computing, 33, pp. 488-496, 2007.
[8] S.Y. Hsieh, G.H. Chen, C.W. Ho, “Longest fault-free paths in star graphs with vertex faults,” Theoret. Comput. pp. 215-227, 2001.
[9] S.Y. Hsieh, G.H. Chen, C.W. Ho, “Longest fault-free paths in star graphs with edge faults,” IEEE Trans. Comput. pp. 960-971, 2001.
[10] S.Y. Hsieh, “Embedding longest fault-free paths onto star graphs with more vertex faults,” Theoret. Comput. pp. 370-378, 2005.
[11] S.Y. Hsieh, C.D. Wu, “Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults,” Journal of Supercomputing, 49, pp. 354-372, 2009.
[12] C.N. Hung, Y.H. Chang, C.M. Sun, “Longest paths and cycles in fault hypercubes,” Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks, pp. 101-110, 2006.
[13] C.W. Huang, H.L. Huang, S.Y. Hsieh, “Edge-bipancyclicity of star graphs with faulty elements,” Theoretical Computer Science, 412, pp. 6938-6947, 2011.
[14] J.S. Jwo, S. Lakshmivarahan, S.K. Dhall, “Embedding of cycles and grids in star graphs,” J. Circuits, Systems, and Comput. pp. 43-74, 1991.
[15] S. Latifi, N. Bagherzadeh, “Hamiltonicity of the clustered-star graph with embedding applications,” Proc. Internat. Conf. Parallel Distributed Process. Tech. pp. 734-744, 1996.
[16] T.K. Li, Jimmy J.M. Tan, L.H. Hsu, “Hyper hamiltonian laceability on edge fault star graph,” Information Sciences, Vol. 165, pp. 59-71, 2004.
[17] T.K. Li, “Cycle embedding in star graphs with edge faults,” Applied Mathematics and Computation, 167, pp. 891-900, 2005.
[18] C.K. Lin, H.M. Huang, L.H. Hsu, “The super connectivity of the pancake graphs and the super laceability of the star graphs,” Theoretical Computer Science, 339, pp. 257-271, 2005.
[19] S. Latifi, “A study of fault tolerance in star graph,” Information Processing Letters, 102, pp. 192-200, 2007.
[20] Z. Miller, D. Pritikin, I.H. Sudborough, “Near embeddings of hypercubes into Cayley graphs on the symmetric group,” IEEE Transaction on Computers, 43, pp. 13-22, 1994.
[21] J.H. Park, H.C. Kim, “Longest paths and cycles in faulty star graphs,” Journal of Parallel and Distributed Computing, 64, pp. 1286-1296, 2004.
[22] S. Ranka, J.C.Wang, N. Yeh, “Embedding meshes on the star graph,” J. Parallel Distributed Comput. pp. 131-135, 1993.
[23] W.Y. Su, C.N. Hung,“The Longest Ring Embedding in Faulty Hypercube,” Workshop on Combinatorial Mathematics and Computational Theory, 23,pp. 262-272, 2006.
[24] Y.C. Tseng, S.H. Chang, J.P. Sheu, “Fault-tolerant ring embedding in star graphs with both link and node failures,” IEEE Trans. Parallel Distributed Systems. pp. 1185-1195, 1997.
[25] Y.C. Tseng, “Embedding a ring in a hypercube with both faulty links and faulty nodes,” Information Processing Letters, 59, pp. 217-222, 1996.
[26] D.J. Wang, “Embedding Hamiltonian cycles into folded hypercubes with link faults,” Journal of Parallel and Distributed Computing, 61, pp. 545-564, 2001.
[27] W.Q. Wang, X.B. Chen, “A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges,” Information Processing Letters, 107, pp. 205-210, 2008.
[28] M.Xu, X.D. Hu, Q. Zhu, “Edge-bipancyclicity of star graphs under edge-fault tolerant,” Applied Mathematics and Computation, 183, pp. 972-979, 2006.
[29] C.Y. Yang, C.N. Hung, “Adjacent Vertices Fault Tolerance Hamiltonian Laceability of Star Graphs” The Proceedings of the 23rd Workshop on Combinatorial Mathematics and Computation Theory, pp. 279-289, 2006.
[30] M.C. Yang, T.K. Li, Jimmy J.M. Tan, L.H. Hsu, “Fault tolerant cycle-embedding of crossed cubes,” Information Processing Letters, 88, pp. 149-154, 2003.
[31] M.C. Yang, “Cycle embedding in star graphs with conditional edge faults,” Applied Mathematics and Computation, 215, pp. 3541-3546, 2009.
[32] M.C. Yang, “Embedding cycles of various lengths into star graphs with both edge and vertex faults,” Applied Mathematics and Computation, 216, pp. 3754-3760, 2010.
[33] M.C. Yang, “Path embedding in star graphs,” Applied Mathematics and Computation, 207, pp. 283-291, 2009.
[34] T.Y. Yu, C.N. Hung, “The Hamiltonian path passing through prescribed edges in a star graph with faulty edges,” Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, pp. 112-123, 2011.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top