Bounds on the number of passes in multistage interconnection networks

摘要

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.