(3.237.97.64) 您好!臺灣時間:2021/03/04 14:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:劉雅惠
研究生(外文):Ya-Hui Liu
論文名稱:最佳多容錯之號誌環網路
論文名稱(外文):Optimal k-Fault-Tolerant Networks for Token Rings
指導教授:徐力行徐力行引用關係
指導教授(外文):Lih-hsing Hsu
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:68
中文關鍵詞:容錯號誌環k漢米爾頓連通圖
外文關鍵詞:fault toleranttoken ringsk-hamiltonian graph.
相關次數:
  • 被引用被引用:0
  • 點閱點閱:64
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
設計一個最佳k容錯之號誌環網路相當於建造一個最佳k漢米爾頓連通圖, 其中k表示點或邊壞掉的個數. 對任意 $V_1 \subset V$, $E_1 \subset E$ 滿足 $\left| V_1 \right|+\left| E_1 \right| \leq k $ 的圖$G=(V,E)$ 被稱為k-漢米爾頓連通圖假如$G-(V_1-E_1)$是漢米爾頓連通圖.
在所有相同點數的k漢米爾頓連通圖裡面, 邊的點數最少的k漢米爾頓連通圖G*是最佳的.
在這篇論文中, 我們證明 是最佳k漢米爾頓連通圖其中k是大於等於4的偶正整數.

Designing an optimal $k$-fault-tolerant network for token rings is equivalent to constructing an optimal $k$-hamiltonian graph, where $k$ is a positive integer and corresponds to the number of faults.
A graph $G=(V,E)$ is $k$-hamiltonian if $G-(V_1-E_1)$ is
hamiltonian for arbitrary $V_1 \subset V$, $E_1 \subset E$ with
$\left| V_1 \right|+\left| E_1 \right| \leq k $. A
$k$-hamiltonian graph G* is optimal if it contains the fewest
edges among all $k$-hamiltonian graphs with the same number of
vertices as G*.
In this thesis, we prove that $G_{n,k}$ is optimal $k$-hamiltonian for $k$ an even integer greater than 4.

中文摘要
英文摘要
誌謝
目錄
圖目錄
第一章 Introduction and Definitions 5
第二章 $G_{n, k}$ is $k$-hamiltonian in Base Group 6
第三章 $G_{n,k}$ is $k$-hamiltonian,$n > 2k$ 12
第四章 Discussion 66

[1] J. Bruck, R. Cypher and C. T. Ho, Fault-tolerant
meshes and hypercubes with minimum numbers of spares, IEEE Trans. Comput. 42 (1993) 1089-1104.
[2] R. S. Chou and L. H. Hsu, 1-edge fault-tolerant design
for meshes, Parallel Processing Letters 4 (1994) 385-389.
[3] S. Dutt and J. P. Hayes, Designing fault-tolerant systems using automorphisms, J. Parallel and Distributed
Computing 12 (1991) 249-268.
[4] Douglas B. West, {\em Introduction to Graph Theory}(Prentice-Hall, Inc, 1996)
[5] R. Gould, {\em Graph Theory}(Benjanmin/Cummings,Menlo Park,CA,1988).
[6] F. Harary and J. P. Hayes, Edge fault tolerant in
graphs, Networks 23 (1993) 135-142.
[7] F. Harary and J. P. Hayes, Node fault tolerant in
graphs, Networks 27 (1996) 19-23.
[8] J. P. Hayes, A graph model for fault-tolerant
computing systems, IEEE Trans. Computers C25 (1976) 875-883.
[9] C. N. Hung, Optimal {\it k}-Fault-Tolerant Networks
for Token Rings, Dissertation in Computer and information
Science, National Chiao Tung University, R.O.C., (1999).
[10] H. K. Ku and J. P. Hayes, Optimally Edge fault
tolerant trees, Networks 27 (1996) 203-214.
[11] F. T. Leighton, Introduction to Parallel Algorithms
and Architectures: Arrays $\cdot$ Trees $\cdot$ Hypercubes,
Morgan Kaufmann Publishers, San Mateo, CA,1992.
[12] K. Mukhopadhyaya and B. P. Sinha, Hamiltonian graphs
with minimum number of edges for fault-tolerant topologies,
Information Processing Letter 44 (1992) 95-99.
[13] M. Paoli, W.W. Wong and C.K. Wong, Minimum {\it
k}-Hamiltonian graphs II, Journal of Grapg Theory 10 (1986)
79-95.
[14] C. J. Shih and K. E. Batcher, Adding multiple-fault tolerant togeneralixed cube networks, IEEE Trans. Parallel and Distributed Systems 5 (1994) 785-792.
[15] T. Y. Sung, M. Y. Lin, and T. Y. Ho,
Multiple-edge-fault tolerant with respect to hypercubes, IEEE
Trans. on Parallel and Distributed Systems 8 (1997) 187-192.
[16] T. Y. Sung, Academia Sinica, T. Y. Ho and L. H.
Hsu, Optimal {\it K}-Fault-Tolerant Networks for Token Rings, accepted by Journal of Information Science and Engineering.
[17] S. Y. Wang, L. H. Hsu and T. Y. Sung, Faithful
1-edge fault tolerant graphs, Information Processing Letter 61
(1997) 173-181.
[18] W.W. Wong and C.K. Wong, Minimum {\it
k}-Hamiltonian graphs, Journal of Grapg Theory 8 (1984)
155-165.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔