ISOMORPHISM OF CONFLICT GRAPHS IN MULTISTAGE INTERCONNECTION NETWORKSAND ITS APPLICATION TO OPTIMAL ROUTING

This paper outlines a study on the isomorphism of conflict graphs in m ultistage interconnection networks (MIN's) and its applications. A new concept called group-transformation is introduced for baseline networ k, which induces an equivalence partition on the set of all permutatio ns. All members belonging to the same equivalence class have isomorphi c conflict graphs. Thus determination of conflict resolution of one pe rmutation, results in determination of conflict resolution of all othe r equivalent members. Next, the BPCL (bit-permute-closure) class of pe rmutations is defined, for which the conflict resolution problem can b e settled in linear time by an earlier algorithm developed only for th e BPC (bit-permute-complement) permutations. It is proved that for an N x N MIN, \BPCL\ greater-than-or-equal-to n! . 2N-1, in contrast to \ BPC\ = n! . 2n, (n = log2 N). Conflict graphs for BPCL permutations ar e also characterized. An O(N2) time algorithm to check membership of a given permutation to the BPCL class, is then described. Finally, all these results are generalized to extend their applicability to other u nique-path full-access MIN's, e.g., omega, reverse baseline, flip, n-c ube, etc.