| A NEW ROUTING ALGORITHM FOR THE SHUFFLE-EXCHANGE PERMUTATION NETWORK |
| |
| 作者姓名： | Baoxing CHEN Wenjun XIA Ni DU |
| |
| 作者单位： | [1]College of Mathematics and System Science, Xinjiang University, Wulumuqi, 830046 [2]Department of Computer Science, Zhangzhou Teacher＇s College, Zhangzhou 363000, China. [3]Department of Computer Science, South China University of Technology, Guangzhou 510641, China. [4]Department of Mathematics, Xiamen University, Xiamen 361005, China. |
| |
| 基金项目： | This work was supported by the Natural Science Foundation of Pujian Province （No. Z0511035） and the Scientific Research Foundation of Fujian Provincial Education Department （No. JA04249）. |
| |
| 摘 要： | 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.
|
| 关 键 词： | 路由算法 交换局 排列网络 直径 |
| 收稿时间： | 2003-10-22 |
| 修稿时间： | 2003-10-222005-10-17 |
A New Routing Algorithm for the Shuffle-Exchange Permutation Network |
| |
| Baoxing CHEN Wenjun XIA Ni DU.A NEW ROUTING ALGORITHM FOR THE SHUFFLE-EXCHANGE PERMUTATION NETWORK[J].Journal of Systems Science and Complexity,2006,19(4):586-591. |
| |
| Authors: | Baoxing Chen Wenjun Xiao Ni Du |
| |
| Institution: | (1) College of Mathematics and System Science, Xinjiang University, Wulumuqi, 830046;(2) Department of Computer Science, Zhangzhou Teacher’s College, Zhangzhou, 363000, China;(3) Department of Computer Science, South China University of Technology, Guangzhou, 510641, China;(4) Department of Mathematics, Xiamen University, Xiamen, 361005, China |
| |
| Abstract: | In this paper,a new routing algorithm is given for the shuffle-exchange permutation network (SEP_n).The length of the path between any two nodes given by our algorithm is not more than (11)/(16)n~2-O(n),i.e.,the diameter of SEP_n is at most(11)/(16)n~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 SEP_n is more than 1/2n~2-n. |
| |
| Keywords: | Cayley graph fixed degree routing shuffle-exchange permutation network |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
|
