跳到主要內容

臺灣博碩士論文加值系統

(3.95.131.146) 您好!臺灣時間:2021/07/25 15:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:塗博勳
研究生(外文):Bo-Syun Tu
論文名稱:星狀圖二可生成性質相鄰點容錯之研究
論文名稱(外文):The Study of the Adjacent Vertices Fault-Tolerance for Two Spannability of Star Graphs
指導教授:洪春男
指導教授(外文):Chun-Nan Hung
口試委員:洪春男徐力行黃鈴玲
口試委員(外文):Chun-Nan HungLih-Hsing HsuLing-Ling Huang
口試日期:2012-06-27
學位類別:碩士
校院名稱:大葉大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:38
中文關鍵詞:星狀圖跨越不相交路徑邊容錯相鄰點容錯
外文關鍵詞:star graphspanning disjoint pathsedges fault toleranceadjacent vertices fault tolerance
相關次數:
  • 被引用被引用: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) be
the n-dimensional star graph. Let P be a path and V(P) be the set of vertices on P. Two
paths 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 adjacent
vertices and Fe be the set of fe faulty edges of Sn. In this thesis, we will show that for
any 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.
目錄
封面內頁
簽名頁
中文摘要…………………………………………………………………iii
ABSTRACT …………………………………………………………iv
誌謝…………………………………………………………………………v
目錄…………………………………………………………………………vi
圖目錄……………………………………………………………………vii
Chapter 1 Introduction……………………………………………………1
Chapter 2 Preliminaries…………………………………………………………4
Chapter 3 The adjacent fault-tolerance for 2-spannability of Sn …………6
Chapter 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 binary
tree 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 star
graphs,” IEICE Trans. Fund. E82-A. pp. 1953-1964, 1999.
[4] Cheng Dongqin and Guo Dachang, “Cycle embedding in star graphs with
more 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 graphs
with 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 graphs
with edge faults,” IEEE Trans. Comput. 50,pp. 960-971, 2001.
[8] S.Y. Hsieh, “Embedding longest fault-free paths onto star graphs with more
vertex faults,” Theoret. Comput. 337,pp. 370-378, 2005.
[9] S.Y. Hsieh and C.D. Wu, “Optimal fault-tolerant Hamiltonicity of star graphs
with 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 Computer
Science, 412, pp.6938-6947, 2011.
[11] Chun-Nan Hung, Yi-Hua Chang, and Chao-Min 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.
[12] Chun-Nan Hung, Chi-Lai Liu and Hsuan-Han Chang, “Edge Fault Tolerance
for Two-Pair Spanning Disjoint Paths,” Proceedings of the 25th Workshop on
Combinatorial Mathematics and Computation Theory. pp. 375-384, 2008.
[13] J.S. Jwo, S. Lakshmivarahan and S.K. Dhall, “Embedding of cycles and grids
in 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 with
embedding applications,” Proc. Internat. Conf. Parallel Distributed Process.
Tech. pp. 734-744, 1996.
[15] Shahram Latifi, “A study of fault tolerance in star graph,” Information Processing
Letters, 102, pp.192-200, 2007.
[16] Tseng-Kuei Li, Jimmy J.M. Tan and Lih-Hsing Hsu, “Hyper hamiltonian
laceability on edge fault star graph,” Information Sciences, 165, pp. 59-71,
2004.
[17] Tseng-Kuei 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 and 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] Z. Miller, D. Pritikin and I.H. Sudborough, “Near embeddings of hypercubes
into 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 Tolerance
Hamiltonian Laceability of Star Graphs,” Proceedings of the 2011 National
Computer Symposium Workshop on Algorithms and Bioinformatics. pp. 65-
71, 2011.
[21] Jung-Heum Park and Hee-Chul 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 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 Faulty
Hypercube,” Proceedings of the 23rd Workshop on Combinatorial Mathematics
and Computational Theory. pp. 262-272, 2006.
[24] Yu-Chee Tseng, S.H. Chang and J.P. Sheu, “Fault-tolerant ring embedding in
star graphs with both link and node failures,” IEEE Transactions on Parallel
and 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 and
faulty nodes,” Information Processing Letters, 59, pp.217-222, 1996.
[27] D. J. Wang, “Embedding Hamiltonian cycles into folded hypercubes with link
faults,” 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 through
prescribed edges in a hypercube with faulty edges,” Information Processing
Letters, 107, pp.205-210, 2008.
[29] Min Xu, Xiao-Dong Hu and Qiang Zhu, “Edge-bipancyclicity of star graphs
under edge-fault tolerant,” Applied Mathematics and Computation, 183,
pp.972-979, 2006.
[30] Ming-Chien Yang, “Path embedding in star graphs,” Applied Mathematics
and Computation, 207, pp.283-291, 2009.
[31] Ming-Chien Yang, “Embedding cycles of various lengths into star graphs with
both edge and vertex faults,” Applied Mathematics and Computation, 216,
pp.3754-3760, 2010.
[32] Ming-Chien Yang, “Cycle embedding in star graphs with conditional edge
faults,” 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 Tolerance
Hamiltonian Laceability of Star Graphs”, The Proceedings of the 23rd Workshop
on Combinatorial Mathematics and Computation Theory, pp. 279-289,
2006.
[35] T.Y. Yu and 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