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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊俊彥
研究生(外文):Chun-Yen Yang
論文名稱:星狀網路的漢米爾頓可蕾絲相鄰點容錯之研究
論文名稱(外文):Adjacent Vertices Fault Tolerance Hamiltonian Laceability of Star Graphs
指導教授:洪春男
指導教授(外文):Chun-Nan Hung
學位類別:碩士
校院名稱:大葉大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:32
中文關鍵詞:星狀網路漢米爾頓可蕾絲
外文關鍵詞:SnHamiltonian laceablehyper-Hamiltonian laceable.Star graphHamiltonian
相關次數:
  • 被引用被引用:0
  • 點閱點閱:190
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
令Sn是n維的星狀網路。在這篇論文裡,我們證明了當有F對壞點且|F|小於等於(n-3)時,Sn是Hamiltonian。當|F|小於等於(n-4)時,Sn是Hamiltonian laceable而且也是hyper-Hamiltonian laceable。根據上面的結果,我們可以證明在有F'個壞點,當|F'|=f'小於等於(n-2)個點時,有長度最少為n!-2f'+2長度的cycle在Sn。當|F'|=f'小於等於(n-3)個點時,有長度最少為n!-2f'+1長度的路徑在任兩個不同顏色的點之間,還有長度最少為n!-2f'長度的路徑在任兩個相同顏色的點之間。
Let Sn be an n-dimensional Star graph. In this paper, we show that Sn −F is Hamiltonian laceable where F is the set of f ≤(n−4) pairs of adjacent faulty vertices, Sn−F is Hamiltonian where F is the set of f ≤(n−3) pairs of adjacent faulty vertices. We also show that Sn −F is hyper-Hamiltonian laceable where F is the set of f ≤(n −4) pairs of adjacent faulty vertices. Applying these results, we also construct the fault-free cycle with length n! −2f + 2 in Sn −F’ where F’ is the faulty vertices set with at least a black vertex and a white vertex for |F’| = f ≤n−2 and the fault-free path with length n! −2f+ 1 for any two different color vertices in Sn−F’where F’is the faulty vertices set with at least a black vertex and a white vertex for |F`| = f ≤n−3 and n!−2f for any two same color vertices in Sn −F′where F′is the faulty vertices set for |F`| = f ≤n−3
封面內頁
簽名頁
授權書                    iii
中文摘要                     iv
英文摘要                      v
誌謝                        vi
目錄                        vii
圖目錄                       viii
表目錄                       ix

Chapter 1  Introduction and Definitions         1
Chapter 2  The Adjacency Hamiltonian Laceablility of Star
Graphs      4
Chapter 3 Fault-free Cycle and Path in Star Graphs with Faulty Vertices 24
Section 3.1. Fault-free Cycle 24
Section 3.2. Fault-free Path 25
Chapter 4 Conclusion    31
Bibliography 32
[1] S. B. Akers and B. Krishnamurthy, “A group-theoretic model for symmetric
interconnection networks,” IEEE Transaction on Computers, 38, pp. 555-566,
1989.
[2] S.B. Akers, D. Harel, B. Krishnamurthy, “The star graph: an attractive alter-
native to the n-cube”, Proc. Internat. Conf. Parallel Processing, pp. 216-223,
1986.
[3] S.G. Akl, “Parallel Computation: Models and Methods, Prentice-Hall”, NJ,
1997.
[4] N. Bagherzadeh, M. Dowd, N. Nassif, “Embedding an arbitrary tree into the
star graph”, IEEE Trans. Comput. pp. 475-481, 1996.
[5] J.C. Bermond (Ed.), “Interconnection networks”, Discrete Appl. Math. 37+38
(1992) (special issue).
[6] R.V. Boppana, S. Chalasani, C.S. Raghavendra, “Resource deadlock and per-
formance of whormhole multicast routing algorithms”, IEEE Trans. Parallel
Distributed Systems pp. 535-549, 1998.
[7] J.H. Chang, C.S. Shin, K.Y. Chwa, “Ring embedding in faulty star graphs”,
IEICE Trans. Fund. E82-A. pp. 1953-1964, 1999.
[8] Y. H. Chang, C. N Hung, “Adjacent Vertices Fault Tolerance Ham-iltonian
Laceability of Hypercube Graphs”, W.C.M.C.T., pp. 301-309, 2005.
[9] M. Y. Chen, S.-J. Lee, “Distributed fault-tolerant embedding of rings in hy-
percubes”, J. Parallel Distrib. Comput. pp. 63-71, 1991.
[10] J. S. Fu, “Fault-tolerant cycle embedding in the hypercube”, Paral-lel Com-
puting, pp. 821-832, 2003.
[11] C. N. Hung, Y. H. Chang, and C. M. Sun, “Longest paths and cycles in
faulty hypercubes,” Proceedings of the IASTED International Conference on
Parallel and Distributed Computing and Networks, pp. 101-110, 2006.
–31–
[12] S. Y. Hsieh, “Embedding longest fault-free paths onto star graphs with more
vertex faults,” Theoretical Computer Science, 337, pp. 370-378, 2005.
[13] 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.
[14] 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.
[15] S.Y. Hsieh, G.H. Chen, C.W. Ho, “Fault-free Hamiltonian cycles in faulty
arrangement graphs”, IEEE Transactions on Parallel and Distributed Systems
10 pp. 223-237, 1993.
[16] D.F. Hsu, “Interconnection Networks and Algorithms”, Networks 23 (4)
(1993) (special issue).
[17] S. Latifi, N. Bagherzadeh, “Hamiltonicity of the clustered-star graph with
embedding applications”, Proc. I.C.P.D.P.T.. pp. 734-744, 1996.
[18] S. Latifi, S.Q. Zheng, N. Bagherzadeh, “Optimal ring embedding in hy-
percubes with faulty links”, Proceedings of the IEEE Sympo-sium on Fault-
Tolerant Computing pp. 178-184, 1992.
[19] T. K. Li, Jimmy J.M. Tan, and L. H. Hsu, “Hyper hamiltonian laceability
on edge fault star graph,” Information Sciences, Vol. 165, pp. 59-71, 2004.
[20] C. K. Lin, H. M. Huanga, and L. H. Hsub,“The super connectivityof the
pancake graphs and the super laceability of the star graphs,” Theoretical
Computer Science, 339, pp. 257-271, 2005.
[21] 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.
[22] Z. Miller, D. Pritikin, and I.H. Sudborough, “Near embeddings of hyper-
cubes into Cayley graphs on the symmetric group,” IEEE Transaction on
Computers, 43, pp. 13-22, 1994.
[23] J. H. Park and H. C. Kim, “Longest paths and cycles in faulty star graphs,”
Journal of Parallel and Distributed Computing, 64, pp. 1286-1296, 2004.
–32–
[24] K. Qiu, S.G. Akl, H. Meijer, On some properties and algorithms for the star
and pancake interconnection networks, J. Parallel Distributed Comput. pp.
16-25, 1994.
[25] S. Ranka, J.C.Wang, N. Yeh, “Embedding meshes on the star graph”, J.
Parallel Distributed Comput. pp. 131-135, 1993.
[26] Abhijit Sengupta, “On ring embedding in hypercubes with faulty nodes and
links”, Information Processing Letters, pp. 207-214, 1998.
[27] Yu-Chee 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.
[28] Y. C. Tseng, Embedding a ring in a hypercube with both faulty links and
faulty nodes, Information Processing Letters, pp. 217-222, 1996.
[29] D.J. Wang, Embedding Hamiltonian cycles into folded hyper-cubes with link
faults, Journal of Parallel and Distributed Com-puting 61 pp. 545-564, 2001.
[30] P.J. Yang, S.B. Tien, C.S. Raghavendra, Embedding of rings and meshes
onto faulty hypercubes using free dimensions, IEEE Transactions on Com-
puters 43 pp. 608-613, 1994.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔