On worst case analysis of permutation routing on data manipulators

This paper deals with the the following problem: given an N×N augmented data manipulator network and a permutation π between its N inputs and outputs, does there exist a polynomial time deterministic algorithm that decides whether π is admissible thorough the network? A number of backtrack search algorithms have been formalized in the literature to solve the problem. None of the published results, however, appear to settle the time complexity of the problem. The goal of this paper is to answer the question positively by showing an O(N^1.695) time bound for solving the problem. The running time is asymptotically optimal, and the given algorithm computes a setting of the switches whenever π is admissible