跳到主要內容

臺灣博碩士論文加值系統

(54.224.117.125) 您好!臺灣時間:2022/01/28 19:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃詠仁
研究生(外文):Yong-Zen Huang
論文名稱:最佳容錯漢米爾頓及漢米爾頓連接圖
論文名稱(外文):Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs
指導教授:徐力行徐力行引用關係
指導教授(外文):Lih-Hsing Hsu
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:29
中文關鍵詞:k連接遞迴式循環圖最佳容錯k-漢米爾頓k-漢米爾頓連接
外文關鍵詞:k-regularrecursive circulant graphsoptimal fault-tolerantk-hamiltoniank-hamiltonian connected
相關次數:
  • 被引用被引用:0
  • 點閱點閱:235
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
當一個k連接漢米爾頓及和米爾頓連接圖損壞k-2及k-3個節點或邊時仍是漢米爾頓及漢米爾頓連接時, 此圖稱為最佳容錯漢米爾頓及漢米爾頓連接圖. 在這篇文章中我們提出一種新的建構方法來建構最佳漢米爾頓及漢米爾頓連接圖.

A k-regular hamiltonian and hamiltonian connected graph G is optimal fault-tolerant hamiltonian and hamiltonian connected if G remains hamiltonian after removing at most k-2 nodes /or edges and remains hamiltonian connected after removing at most k-3 nodes /or edges. In this paper, we investigate a construction scheme to construct optimal fault-tolerant hamiltonian and hamiltonian connected graphs.

1 Introduction
2 Main result
3 Proof of Lemma 1
4 Proof of Lemma 2
5 Conclusion
6 References

S. B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Computers 38 (1989),555--566.
L. Bhuyan and D. P. Agrawal, Generalized hypercube and hyperbus structures for a computer network,IEEE Trans. Computers 33 (1984), 323--333.
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York, 1980.
Fouad B. Chedid, On the generalized twisted cube,Info. Processing Letters 55 (1995) 49--52.
Y. C. Chen, C. H. Tsai, L. H. Hsu, and Jimmy J. M. Tan, Construction schemes of fault-tolerant Hamiltonian graphs, Proceedings of ISAS SCI 2001 5 (2001),183--187.
D. R. Duh, G. H. Chen, and D. F. Hsu, Combinatorial properties of generalized hypercube graphs, Info. Processing Letters 57 (1996), 41--45.
W. T. Huang, Y. C. Chuang, J. M. Tan, and L. H. Hsu, Fault-free hamiltonian cycle in faulty Möbius Cubes, J. Computing and Sys., 4 (2000), 106--114.
W. T. Huang, M. Y. Lin, J. M. Tan, and L. H. Hsu, ``Fault-tolerant ring embedding in faulty crossed cubes", Proceeding of World Multiconf. Sys., Cybernetics. and Infor. SCI'2000 $IV$, 2000, pp. 97--102.
W. T. Huang, J. M. Tan, C. N. Hung, and L. H. Hsu, ``Token ring embedding in faulty twisted cubes", Proceeding of the 2'nd Inter. Conf. Parallel Sys. PCS'99, 1999, pp. 1--10.
S. Latifi, S. Q. Zheng, and N. Bagherzadeh, ``Optimal ring embedding in hypercubes with faulty links", Proceedings of the IEEE Symposium on Fault-Tolerant Computing, 1992, pp. 178--184.
Y. R. Leu and S. Y. Kuo, Distributed fault-tolerant ring embedding and reconfiguration in hypercubes, IEEE Trans. Computers 48 (1999), 81--88.
R. A. Rowley and B. Bose, Fault-tolerant ring embedding in de-Bruijn networks, IEEE Trans. Computers 12 (1993), 1480--1486.
A. Sengupta, On ring embedding in hypercubes with faulty nodes and links, Infor. Processing Letters 68 (1998), 207--214.
T. Y. Sung, C. Y. Lin, Y. C. Chuang, and L. H. Hsu, Fault tolerant token ring embedding in double loop networks, Infor. Processing Letters 66 (1998), 201--207.
C. H. Tsai, J. M. Tan, Y. C. Chuang, and L. H. Hsu, ``Fault-free cycles and links in faulty recursive circulant graphs", Proceedings of the 2000 International Computer Symposium, 2000, pp. 74--77.
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 Trans. on Parallel and Distributed Sys. 8 (1997), 1185--1195.
P. Cull, and S. M. Larson, The Möbius Cubes, IEEE Trans. Computers. 44 (1995), 647--659.
K. Efe, The The Crossed Cube Architecture for Parallel Computation, IEEE Trans. on Parallel and Distributed Sys. 3 (1992), 513--524.
Douglas B.West, Introduction to graph theory, Prentice-Hall. (1996).
P. A. J Hillbers, M. R. J. Koopman, and J. L. A. van de Snepscheut,
The Twisted cube, in Parallel Architectures and Languages Europe, Lecture Notes in Computer Science. (1987), 152--159.

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