(3.238.99.243) 您好!臺灣時間:2021/05/15 20:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:毛信惟
研究生(外文):Mao,HsinWei
論文名稱:交叉立方體的特殊容錯漢米爾頓連通性
論文名稱(外文):On some special fault-tolerant Hamiltonian connectedness of crossed cubes
指導教授:龔自良
指導教授(外文):Kung,TzuLiang
口試委員:陳宏昌沈偉誌龔自良
口試委員(外文):Chen,HungChangShen,WeiChihKung,TzuLiang
口試日期:2013-01-24
學位類別:碩士
校院名稱:亞洲大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:114
中文關鍵詞:漢米爾頓連通容錯漢米爾頓連通
外文關鍵詞:Hamiltonian connectedfault-tolerant Hamiltonian connected
相關次數:
  • 被引用被引用:0
  • 點閱點閱:121
  • 評分評分:
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
交叉立方體(Crossed Cube)是超立方體(Hypercube)的一種變形,n維度交叉立方體CQn是一種規則圖形且有2n個點及n2n-1條連線,其直徑(diameter)約略只有超立方體的一半。在本論文當中我們討論交叉立方體的結構特性列舉如下:
1. 令u為CQn的任意點,(x,y)為CQn-{u}的任意邊,n≥5,則CQn-{u,x,y}是漢米爾頓連通。
2.令(u,v) and (x,y)為CQn的任意兩組vertex-disjoint edge,n≥5,則CQn-{u,v,x,y}是為漢米爾頓連通。
3.令P為CQn中長度是(n-3)的任意路徑,n≥5,則CQn-V(P)是漢米爾頓連通,其中V(P)表示路徑P上的點集合。
4.令w為CQn的任意點,n≥4,(u,v)是CQn-{w}的i-維度邊,2≦i≦n,則對於3≦l≦2n-2,在CQn-{w}中存在一條長度為l的路徑且連接u和v兩點。
關鍵字:漢米爾頓連通、容錯漢米爾頓連通

The crossed cube is one of the most notable variations of hypercubes. The n-dimensional crossed cube CQn has 2n vertices and n2n-1 edges. In this thesis, we study some topological properties of crossed cubes as follows:
1. Let u be any vertex of CQn and (x,y) be any edge of CQn-{u}, n≧5. Then, CQn-{u, x, y} is Hamiltonian connected.
2. Let (u, v) and (x, y) be any two vertex-disjoint edges of CQn, n≧5. Then, CQn-{u, v, x, y} is Hamiltonian connected.
3. Let P be any path of length n-3 in CQn, n≧5. Then, CQn-V(P) is Hamiltonian connected.
4. Let w be any vertex of CQn, n≧4. Suppose that (u,v) is an i-dimensional edge of CQn-{w}, 2≦ i≦n. Then, for 3≦l≦2n-2, there exists a path of length l joining u and v in CQn-{w}.





Keyword: Hamiltonian connected、fault-tolerant Hamiltonian connected

Abstract(Chinese)………………………………………………….. i
Abstract(English)…………………………………………………… ii
誌謝…………………………………………………………………. iii
Contents……………………………………………………………… iv
List of Figure…………………………………………………………. v
1 Introduction………………………………………………………… 1
1.1 Preliminary……………………………………………………... 3
1.2 Related works…………………………………………………… 5
2 The crossed cube and its properties…………………………………. 10
3 Fault-tolerant Hamiltonian connectedness of CQn………………….. 15
4 Conclusion…………………………………………………………… 23
References……………………………………………………………. 24
簡歷........................................................................................................ 29
Appendix A……………………………………………………………. 30
Appendix B……………………………………………………………. 59
Appendix C……………………………………………………………. 67
Figure 1 Illustration of CQ3 and CQ4………………………………….. 11
Figure 2 Case 1 in the proof of Lemma 7……………………………… 21
Figure 3 Proof in Theorem 2…………………………………………… 22

[1] Y. Alavi and J.E. Williamson, “Panconnected graphs”, STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA. vol. 10, pp. 19–22, 1975.
[2] J.A. Bondy, “Pancyclic graphs”, JOURNAL OF COMBINATORIAL THEORY SERIES B 11, pp. 80–84, 1971.
[3] J.A. Bondy and U.S.R. Murty, “Graph Theory”, Springer, London, 2008.
[4] A. Broder, F. Frieze and E. Upfal, “Existence and Construction of Edge-Disjoint Paths on Expander Graphs”, SIAM JOURNAL ON COMPUTING, vol. 23, pp. 976-989, 1994.
[5] M.Y. Chan and S.-J. Lee, “Fault-Tolerant Embedding of Complete Binary Trees in Hypercubes” IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 3, pp. 277-288, Mar. 1993.
[6] C.-P. Chang, T.-Y. Sung and L.-H. Hsu, “Edge Congestion and Topological Properties of Crossed Cubes” IEEE Transactions on Parallel and Distributed Systems , vol. 11, no. 1, pp. 64-80, Jan. 2000.
[7] C. P. Chang and C. C. Wu, “Conditional Fault Diameter of Crossed Cubes”, Journal of Parallel and Distributed Computing, vol. 69, pp. 91-99, 2009.
[8] J.-M. Chang, J.-S. Yang, H.-L. Wang and Y. Cheng, “Panconnectivity, Fault Tolerant Hamiltonicity and Hamiltonian-connectivity in Alternating Group Graphs”, Networks, Vol. 44, No 4, pp. 302-311, 2004.
[9] Hon-Chan Chen, Tzu-Liang Kung, Lih-Hsing Hsu, “Embedding a Hamiltonian cycle in the crossed cube with two required vertices in the fixed positions ”, Applied Mathematics and Computation. Vol. 217, pp. 10058–10065, 2011.
[10] K. Efe, “A Variation on the Hypercube with Lower Diameter,” IEEE Transactions on Computers, vol. 40, no. 11, pp. 1312-1316, Nov. 1991.
[11] K. Efe, “The Crossed Cube Architecture for Parallel Computing”, IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513–524, 1992.
[12] K. Efe, P. K. Blackwell, W. Slough and T. Shiau, “Topological Properties of the Crossed Cube Architecture”, Parallel Computing, vol. 20, pp. 1763–1775, 1994.
[13] J. Fan, X. Lin and X. Jia, “Node-pancyclicity and edge-pancyclicity of crossed cubes”, Information Processing Letters. vol. 93, pp. 133–138, 2005.
[14] J. Fan, X. Lin and X. Jia, “Optimal path embedding in crossed cubes ”, IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 12, pp. 1190-1200, 2005.
[15] Q.-P. Gu and S. Peng, “Optimal Algorithms for Node-to-Node Fault Tolerant Routing in Hypercubes”, Computer J., vol. 39, no. 7, pp. 626-629, July 1996.
[16] Q.-P. Gu and S. Peng, “Unicast in Hypercubes with Large Number of Faulty Nodes”, IEEE Transactions on Parallel and Distributed Systems, vol. 10,
no. 10, pp. 964-975, Oct. 1999.
[17] S.-Y. Hsieh, G.-H. Chen and C.-W. Ho, “Longest Fault-Free Paths in Star Graphs with Vertex Faults”, Theoretical Computer Science, vol. 262, nos. 1-2, pp. 215-227, 2001.
[18] L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks, CRC Press, 2008
[19] W.-T. Huang, Y.-C. Chuang, J.-M. Tan and L.-H. Hsu, “On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, vol. E85-A, no. 6, pp. 1359–1370, 2002.
[20] S.-S. Kao, C.-K. Lin, H.-M. Huang and L.-H. Hsu, “Panpositionable Hamiltonian graphs”, ARS COMBINATORIA. Vol. 81, pp. 209–223, 2006.
[21] P. Kulasinghe, “Connectivity of the Crossed Cube,” Information Processing Letters, vol. 61, pp. 221-226, July 1997.
[22] P. Kulasinghe and S. Bettayeb, “Embedding Binary Trees into Crossed Cubes”, IEEE Transactions on Computers, vol. 44, no. 7, pp. 923-929, July 1995.
[23] J. Kzeinberg and E. Tardos, “Disjoint Paths in Densely Embedded Graphs”, Proc. 36th Ann. Symp. Foundations of Computer Science, pp. 52-61, Oct. 1995.
[24] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes, Morgan Kaufman, San Mateo, 1992.
[25] X. Lin, P.K. Mckinley, and L.M. Ni, “Deadlock-Free Multicast Wormhole Routing in 2D Mesh Multicomputers,” IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 8, pp. 793-804, Aug.1994.
[26] X. Lin and L.M. Ni, “Deadlock-Free Multicast Wormhole Routing in Multicomputer Networks”, Proceedings 18th Annual Int’l Symposium Computer Architecture, pp. 116-125, 1991.
[27] J.-H. Park, H.-C. Kim and H.-S. Lim, “Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements”, IEEE Transactions on Parallel and Distributed Systems. vol.17, pp. 227–240, 2006
[28] Y. Saad and M.H. Shultz, “Topological properties of hypercubes”, IEEE Transactions on Computers. vol. 37, pp. 867–872,1988.
[29] Y.-C. Tseng, S.-H. Chang and J.-P. Sheu, “Fault-Tolerant Ring Embedding in a Star Graph with Both Link and Node Failures”, IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185- 1195, Dec. 1997.
[30] J.-M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht/Boston/London, 2001.
[31] M.-C. Yang, T.-K. Li, J.J.M. Tan and L.-H. Hsu, “Fault-Tolerant Cycle-Embedding of Crossed Cubes”, Information Processing Letters, vol. 88, no. 4, pp. 149-154, Nov. 2003.



QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top