Rearrangeability of the Tandem Cascade of Banyan-type Networks
Xuesong Jonathan Tan, Shuo Li, Yuxiu Shen · 2005
The cascade of two 2^n × 2^n baseline networks in tandem and the cascade of two omega networks through a special interconnection pattern are known to be rearrangeable. These belong to the general problem: for what two banyan-type networks (i.e., bitpermuting unique-routing network) are their tandem cascade a rearrangeable network? We relate the problem to the trace and guide of banyan-type networks. When the guide of one 2^n × 2^n banyan-type network and the trace of the other are represented by the permutations y and t on integers 1 to n, respectively, rearrangeability of their tandem cascade is solely determined by yt^-1, which is said to be a tandem rearrangeable permutation when the tandem cascade is indeed rearrangeable. We identify a few tandem rearrangeable permutations, each implying the rearrangeability of the tandem cascade of a wide class of banyan-type networks.