Bounds on the number of passes in multistage interconnection networks
Yashovardhan R. Potlapalli, Dharma Prakash Agrawal · 2002
Determining the exact number of passes required to realize a permutation on a multistage interconnection network (MIN) is known to be an /spl Nscr//spl Pscr/ Complete problem. We present a new characteristic of conflicts in MINs which makes conflict detection easier. We use this important property to develop a polynomial time algorithm to determine strong upper and lower bounds on the number of passes required to realize a permutation.>