Conflict resolutions in the inside-out routing algorithm

We recently proposed a new algorithm which routes a class of 2log ₂N- or (2log₂N-1)-stage rearrangeable networks. Although we discussed some of the general rules for proper routing, detailed strategies for resolving possible conflicts were not mentioned. In this paper, we point out additional conditions which enable conflict-free routing in the original algorithm. Cyclic property at the center stages is analyzed in more detail. We also show that the routing problem in the concatenation of two omega networks known as 2log₂ N-stage shuffle network, is in the class of NP-completeness