標題: 有錯單一方向性之超立方體中環形圖之嵌入
Fault-Free Ring Embedding in Faulty Uni-directional Hypercube
作者: 曾偉富
徐力行
Lih-Hsing Hsu
資訊科學與工程研究所
關鍵字: 漢彌爾頓環路;容錯;超立方體;單一方向性超立方體;hypercube;uni-directional hypercube;fault-tolerant;hamiltonian
公開日期: 2000
摘要: 在這篇論文裡,我們針對單一方向性的超立方體 (UQn) 結構, 做進一步的研究, 首先, 在UQn中, 在n 是偶數且 n 大於或等於 4 的情況下, 當 UQn 最多發生 (n-2)/2 條連接線錯誤時, 我們證明它可以內含一個漢彌爾頓環路, 而這是最佳的結果。 進而, 我們證明出當 UQn 中發生的連接線和節點的錯誤總和小於或等於 (n-2)/2 時, UQn 裡依然可以內含一個長度為 2n - 4fv 的漢彌爾頓環路 (fv為錯誤節點之數量)。
A uni-directional hypercube, denoted UQn, is an n-dimensional hypercube, denoted Qn, with simplex uni-directional links. While accommodating large number of nodes, UQn requires less complicated communication than the hypercubes. In addition, they alleviate the pin-limitation problem encountered in fabricating VLSI hypercubes and allow hypercube implementation of the Metropolitan Area Networks using optical fiber links. In this paper, we prove that UQn is (n-2)/2 - edge hamiltonian. That is, in UQn, up to (n-2)/2 links can fail without destroying all available hamiltonian cycles. This result is optimal. Moreover, we prove that a ring of length 2n - 4fv can be embedded in a faulty UQn with |fe| + |fv| (n-2)/2 faulty edges and vertices where fe are faulty edges and fv are faulty nodes.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT890394044
http://hdl.handle.net/11536/66947
Appears in Collections:Thesis