標題: Rearrangebility of bit permutation networks
作者: Bao, XW
Hwang, FK
Li, Q
應用數學系
Department of Applied Mathematics
關鍵字: multistage interconnection network;rearrangeability;layered cross product;permutation;balanced matrix
公開日期: 7-Mar-2006
摘要: In this paper, we introduce the concept of routing grid as a tool for analyzing realizability of permutations on bit permutation networks (BPNs). We extend a result by Linial and Tarsi which characterizes permutations realizable on shuffle-exchange networks to any BPNs. A necessary condition for a BPN to be rearrangeable is given, and the rearrangeability of two families of BPNs are explored. Finally, we present a method which may help to tackle one kind of balanced matrix problems whose solution implies an answer to Benes conjecture. Hopefully, our treatment brings some new insight into the problem of permutation routing. (c) 2005 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tcs.2005.09.077
http://hdl.handle.net/11536/12494
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2005.09.077
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 352
Issue: 1-3
起始頁: 197
結束頁: 214
Appears in Collections:Articles