# 臺灣博碩士論文加值系統

(3.95.131.146) 您好！臺灣時間：2021/07/25 15:32

:::

### 詳目顯示

:

• 被引用:0
• 點閱:106
• 評分:
• 下載:0
• 書目收藏:0
 在連結網路中Star graph 是一個耳熟能詳的拓樸網路架構。Sn是n 維星狀圖。此論文中探討星狀圖二可生成性質相鄰點容錯。在Sn 上兩條路徑P1和P2是兩條跨越不相交路徑。先令Fe 是Sn 上壞邊的集合和Fav 是Sn 上相鄰壞點對數的集合。我們要證明的是在Sn≥5， Sn − Fe − Fav 時有∣Fe∣+∣Fav∣≤ n – 4，再任給2 對不同顏色的點s1, s2 ∈ V0 和 t1, t2 ∈ V1，我們能找到兩條路徑把所有的點都走完，而且互不相交。
 The star graph is a famous interconnection networks. Let Sn = (V0 ∪ V1, E) bethe n-dimensional star graph. Let P be a path and V(P) be the set of vertices on P. Twopaths P1 and P2 are two spanning disjoint paths of Sn = (V0 ∪ V1, E) if V(P1) ∩V(P2) = ∅ and V(P1)∪ V(P2) = V0 ∪ V1. Let Fav be the set of fav pairs of adjacentvertices and Fe be the set of fe faulty edges of Sn. In this thesis, we will show that forany s1, s2 ∈V0 and t1, t2 ∈ V1, there exist two spanning disjoint paths P(s1, t1) and P(s2,t2) of Sn - Fav – Fe for fav + fe ≤ n-4 and n ≥ 5.
 目錄封面內頁簽名頁中文摘要…………………………………………………………………iiiABSTRACT …………………………………………………………iv誌謝…………………………………………………………………………v目錄…………………………………………………………………………vi圖目錄……………………………………………………………………viiChapter 1 Introduction……………………………………………………1Chapter 2 Preliminaries…………………………………………………………4Chapter 3 The adjacent fault-tolerance for 2-spannability of Sn …………6Chapter 4 Conclusion……………………………………………………26
 References[1] S.B. Akers, B. Krishnamurthy, “A group-theoretic model for symmetric in-terconnection networks,” IEEE Transaction on Computers, 38, pp. 555-566,1989.[2] N. Bagherzadeh, M. Dowd and N. Nassif,“ Embedding an arbitrary binarytree into the star graph,” IEEE Trans. Comput. 45,pp. 475-481, 1996.[3] J.H. Chang, C.S. Shin and K.Y. Chwa,“ Ring embedding in faulty stargraphs,” IEICE Trans. Fund. E82-A. pp. 1953-1964, 1999.[4] Cheng Dongqin and Guo Dachang, “Cycle embedding in star graphs withmore conditional faulty edges,” Applied Mathematics and Computation, 218,pp.3856-3867, 2011.[5] Jung-Sheng Fu, “Conditional fault-tolerant hamiltonicity of star graphs,”Parallel Computing, 33, pp.488-496, 2007.[6] S.Y. Hsieh, G.H. Chen and C.W. Ho, “Longest fault-free paths in star graphswith vertex faults,” Theoret. Comput. 262,pp. 215-227, 2001.[7] S.Y. Hsieh, G.H. Chen, C.W. Ho, “Longest fault-free paths in star graphswith edge faults,” IEEE Trans. Comput. 50,pp. 960-971, 2001.[8] S.Y. Hsieh, “Embedding longest fault-free paths onto star graphs with morevertex faults,” Theoret. Comput. 337,pp. 370-378, 2005.[9] S.Y. Hsieh and C.D. Wu, “Optimal fault-tolerant Hamiltonicity of star graphswith conditional edge faults,” Journal of Supercomputing, 49, pp.354-372,2009.[10] Chao-Wen Huang, Hui-Ling Huang and Sun-Yuan Hsieh, “Edge-bipancyclicity of star graphs with faulty elements,” Theoretical ComputerScience, 412, pp.6938-6947, 2011.[11] Chun-Nan Hung, Yi-Hua Chang, and Chao-Min Sun, “Longest paths andcycles in fault hypercubes,” Proceedings of the IASTED International Conferenceon Parallel and Distributed Computing and Networks. pp. 101-110,2006.[12] Chun-Nan Hung, Chi-Lai Liu and Hsuan-Han Chang, “Edge Fault Tolerancefor Two-Pair Spanning Disjoint Paths,” Proceedings of the 25th Workshop onCombinatorial Mathematics and Computation Theory. pp. 375-384, 2008.[13] J.S. Jwo, S. Lakshmivarahan and S.K. Dhall, “Embedding of cycles and gridsin star graphs,” Journal of Circuits, Systems and Computers, 1, pp. 43-74,1991.[14] S. Latifi and N. Bagherzadeh, “Hamiltonicity of the clustered-star graph withembedding applications,” Proc. Internat. Conf. Parallel Distributed Process.Tech. pp. 734-744, 1996.[15] Shahram Latifi, “A study of fault tolerance in star graph,” Information ProcessingLetters, 102, pp.192-200, 2007.[16] Tseng-Kuei Li, Jimmy J.M. Tan and Lih-Hsing Hsu, “Hyper hamiltonianlaceability on edge fault star graph,” Information Sciences, 165, pp. 59-71,2004.[17] Tseng-Kuei Li, “Cycle embedding in star graphs with edge faults,” AppliedMathematics and Computation, 167, pp.891-900, 2005.[18] C.K. Lin, H.M. Huang and L.H. Hsu, “The super connectivity of the pancakegraphs and the super laceability of the star graphs,” Theoretical ComputerScience, 339, pp. 257-271, 2005.[19] Z. Miller, D. Pritikin and I.H. Sudborough, “Near embeddings of hypercubesinto Cayley graphs on the symmetric group,” IEEE Transaction on Computers, 43, pp. 13-22, 1994.[20] Tsung-Han Ou and Chun-Nan Hung, “The Adjacent Vertices Fault ToleranceHamiltonian Laceability of Star Graphs,” Proceedings of the 2011 NationalComputer Symposium Workshop on Algorithms and Bioinformatics. pp. 65-71, 2011.[21] Jung-Heum Park and Hee-Chul Kim, “Longest paths and cycles in faulty stargraphs,” Journal of Parallel and Distributed Computing, 64, pp.1286-1296,2004.[22] S. Ranka, J.C.Wang and N. Yeh, “Embedding meshes on the star graph,”Journal of Parallel and Distributed Computing, 19, pp. 131-135, 1993.[23] Wen-Yan Su and Chun-Nan Hung, “The Longest Ring Embedding in FaultyHypercube,” Proceedings of the 23rd Workshop on Combinatorial Mathematicsand Computational Theory. pp. 262-272, 2006.[24] Yu-Chee Tseng, S.H. Chang and J.P. Sheu, “Fault-tolerant ring embedding instar graphs with both link and node failures,” IEEE Transactions on Paralleland Distributed Systems, 8, pp. 1185-1195, 1997.[25] Chang-Hsiung Tsai, Jimmy J.M. Tan, Tyne Liang, and Lih-Hsing Hsu, “Fault-tolerant hamiltonian laceability of hypercubes,” Information Processing Letters, 83, pp. 301-306, 2006.[26] Y. C. Tseng, “Embedding a ring in a hypercube with both faulty links andfaulty nodes,” Information Processing Letters, 59, pp.217-222, 1996.[27] D. J. Wang, “Embedding Hamiltonian cycles into folded hypercubes with linkfaults,” Journal of Parallel and Distributed Computing, 61, pp.545-564, 2001.[28] W. Q. Wang and X.B. Chen, “A fault-free Hamiltonian cycle passing throughprescribed edges in a hypercube with faulty edges,” Information ProcessingLetters, 107, pp.205-210, 2008.[29] Min Xu, Xiao-Dong Hu and Qiang Zhu, “Edge-bipancyclicity of star graphsunder edge-fault tolerant,” Applied Mathematics and Computation, 183,pp.972-979, 2006.[30] Ming-Chien Yang, “Path embedding in star graphs,” Applied Mathematicsand Computation, 207, pp.283-291, 2009.[31] Ming-Chien Yang, “Embedding cycles of various lengths into star graphs withboth edge and vertex faults,” Applied Mathematics and Computation, 216,pp.3754-3760, 2010.[32] Ming-Chien Yang, “Cycle embedding in star graphs with conditional edgefaults,” Applied Mathematics and Computation, 215, pp.3541-3546, 2009.[33] M. C. Yang, T.K. Li, Jimmy J.M. Tan and L.H. Hsu, “Fault tolerant cycle-embedding of crossed cubes,” Information Processing Letters, 88, pp.149-154,2003.[34] Chun-Yen Yang and Chun-Nan Hung, “Adjacent Vertices Fault ToleranceHamiltonian Laceability of Star Graphs”, The Proceedings of the 23rd Workshopon Combinatorial Mathematics and Computation Theory, pp. 279-289,2006.[35] T.Y. Yu and C.N. Hung, “The Hamiltonian path passing through prescribededges in a star graph with faulty edges,” Proceedings of the 28th Workshopon Combinatorial Mathematics and Computation Theory, pp. 112-123, 2011.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 星狀圖的漢米爾頓可蕾絲相鄰點容錯之研究 2 星狀網路通過特定邊的漢米爾頓迴圈與漢米爾頓路徑邊容錯之研究

 無相關期刊

 1 以投影法為基礎之工程圖影像字元萃取法 2 星狀圖的漢米爾頓可蕾絲相鄰點容錯之研究 3 結合基因演算法與雲端技術求解旅行家問題應用於行動裝置 4 表演藝術之戲劇體驗劇－田家樺創作論述 5 智慧家庭控制系統 6 同時考量佈局面積與TSV線長的3D IC 之TSV擺置方法設計 7 以整數線性規劃法解決全客戶式 超大型積體電路增量式平面規劃 8 工程圖影像字元萃取之研究與實作 9 應用認知負荷理論為基之數位學習於圓面積學習成效改善 10 應用地圖軟體為基之數位學習系統改善學生地圖認知 11 使用微型叫號器改善醫院門診叫號系統 12 交叉立方體條件式容錯漢米爾頓迴路 13 以整數線性規劃法解決大型全客戶式超大型積體電路增量式平面規劃 14 一個以影像處理為基礎的移動追蹤系統 - 應用於微流體流動監控下的速度即時偵測與評估 15 區塊式主成分析及線性別在人臉辨識之研究

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