(3.238.99.243) 您好！臺灣時間：2021/05/15 20:10

### 詳目顯示:::

:

• 被引用: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)………………………………………………….. iAbstract(English)…………………………………………………… ii誌謝…………………………………………………………………. iiiContents……………………………………………………………… ivList of Figure…………………………………………………………. v1 Introduction………………………………………………………… 1 1.1 Preliminary……………………………………………………... 3 1.2 Related works…………………………………………………… 52 The crossed cube and its properties…………………………………. 103 Fault-tolerant Hamiltonian connectedness of CQn………………….. 154 Conclusion…………………………………………………………… 23 References……………………………………………………………. 24 簡歷........................................................................................................ 29 Appendix A……………………………………………………………. 30 Appendix B……………………………………………………………. 59 Appendix C……………………………………………………………. 67Figure 1 Illustration of CQ3 and CQ4………………………………….. 11Figure 2 Case 1 in the proof of Lemma 7……………………………… 21Figure 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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 在交叉立方體中建構一對多之平行路徑 2 在交叉立方體上之完整適應性容錯演算法 3 The Study of Routing Protocol Based on Bit Map Table 4 各類機器學習方法在太陽黑子數目預測上之效能評估 5 交叉立方體條件式容錯漢米爾頓迴路 6 交錯式立方體之容錯與嵌入特性：條件式容錯直徑、漢米爾頓路徑及嵌入金字塔網路 7 交叉立方體結構之三回合動態診斷研究 8 階層式交叉立方體中兩條互斥等長之路徑涵蓋問題研究 9 資訊圖表應用於國中地理教學學習成效之研究—以苗栗縣立苑裡高級中學國中部為例 10 國際疾病分類第十版ICD-10-PCS手術給碼輔助系統開發 11 運用OpenFlow於雲端虛擬交換器監控系統之實作 12 以粒子群最佳化演算法加速之Zigbee Access Point 布置規劃 13 以平行計算求解 彈性製程之零工式生產排程最佳化 14 台灣工具機產業機械加工特質與精實變革 15 中彰地區教保服務人員資訊科技素養對SET系統使用者態度之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室