有錯單一方向性之超立方體中環形圖之嵌入

Abstract

在這篇論文裡,我們針對單一方向性的超立方體 (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.