摘要
在这篇论文,一个新路由算法为 shuffle-exchangepermutation 网络(SEP_n ) 被给。在我们的算法给的任何二个节点之间的路径的长度是不超过 11/16 n^2 + O (n) ,即, SEP_n 的直径是至多 11/16 n^2 + O (n) 。1/8 上的 Thisimproves (9n ~ 2 - 22n + 24 ) S 更早描述的路由算法。Latifi 和 P。K.Srimani。我们也证明 SEP_n 的直径多于 1/2 n^2 - n。
In this paper, a new routing algorithm is given for the shuffle-exchange permutation network (SEPn). The length of the path between any two nodes given by our algorithm is not more than 11/16n^2+O(n), i.e., the diameter of SEPn is at most 11/16n^2+ O(n). This improves on a 1/8(9n^2- 22n+24) routing algorithm described earlier by S. Latifi and P. K. Srimani. We also show that the diameter of SEPn is more than 1/2n^2-n.
基金
This work was supported by the NatLiral Science Foundation of Fujian Provmce(No.Z0511035)
the Scientific Research Foundation of Fujian Provincial Education Department(No.JA04249)
关键词
路由算法
交换局
排列网络
直径
Cayley graph, fixed degree, routing, shuffle-exchange permutation network.