Rearrangebility of bit permutation networks
檔案
- 000235826900014.pdf (354.2 KB, Adobe PDF)
日期
2006-03-07
類型
系所
期刊名稱
THEORETICAL COMPUTER SCIENCE
卷期與頁次
第 352 卷第 1-3 期,頁 197–214
ISSN
0304-3975
語言
英文
摘要
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.