Fast permutation routing in a class of interconnection networks

This paper considers the following permutation routing problem: Given an N x N augmented data manipulator (ADM) network and a permutation pi between its N inputs and outputs, can all the traffic connections of pi be routed through the network in one pass? A number of backtrack search algorithms have been devised for recognizing ADM admissible permutations. None of the published results, however, appears to settle the time complexity of the problem. The goal of this paper was to answer the question positively by showing the first polynomial time bound for solving the problem. The devised algorithm requires O(N-1.695) time to decide whether a given permutation pi is admissible and compute a setting of the switches whenever pi is admissible. For many practical applications, the obtained bound compares favorably with the O(N Ig N) size of an N-input ADM network. (C) 2002 Wiley Periodicals, Inc.