摘要
目的研究在Ｆｉｂｏｎａｃｃｉ立方网络Γｎ（ｎ≥６）中寻找任意两个结点Ｓ和Ｄ之间的两条平行路径的寻径问题，并最终为实现多处理器系统中各处理器之间的信息传递提供理论依据．方法将Γｎ抽象为一个“图”进行研究．结果给出了相应的寻径算法．如果ｍ＝ｍｉｎ｛ｌ：Ｓ＜ｆｌ，Ｄ＜ｆｌ｝，则求出的两条路径满足：｜Ｐｉ（Ｓ，Ｄ）｜≤２ｍ－５，ｉ＝１，２．
Aim To study the routing problem of finding two parallel paths between arbitrary two nodes S and D on Fibonacci cube of order n, Γ n , and provide the theoretical basis for message exchange among processors in multiprocessors systems. Methods Γ n was abstracted as a ‘graph’ and studied in graph theory. Results The corresponding routing algorithm is given. If m =min{ l:S<f l,D<f l }, the paths obtained by our algorithms satisfy | P i(S,D)|≤2m-5 , for i =1,2. Conclusion This will be useful for some applications in fault tolerant routing on some interconnection networks such as Hypercube and mesh.
出处
《北京理工大学学报》
EI
CAS
CSCD
1999年第2期180-185,共6页
Transactions of Beijing Institute of Technology
