Title: | Rearrangebility of bit permutation networks |
Authors: | Bao, XW Hwang, FK Li, Q 應用數學系 Department of Applied Mathematics |
Keywords: | multistage interconnection network;rearrangeability;layered cross product;permutation;balanced matrix |
Issue Date: | 7-Mar-2006 |
Abstract: | 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 |
Journal: | THEORETICAL COMPUTER SCIENCE |
Volume: | 352 |
Issue: | 1-3 |
Begin Page: | 197 |
End Page: | 214 |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.