Analysis of conflict graphs in multistage interconnection networks
Nabanita Das, Bhaswar B. Bhattacharya, Jayasree Dattagupta · 2002
For multistage interconnection networks (MINs), the authors introduce a concept called group transformation that partitions the set of all permutations into several equivalence classes, such that all members belonging to the same class have isomorphic conflict graphs. The authors then define the BPCL (bit-permute-closure) class of permutations and show that the conflict resolution problem can be settled in linear time for BPCL by an earlier algorithm developed by Raghavendra and Varma (see IEEE Trans.Comput., vol. C-35, no.4, 1986) for BPC (bit-permute-complement) permutations only. The ability to apply Raghavendra's algorithm is enhanced to a great extent. The authors also describe an O(N/sup 2/) algorithm to decide whether or not a given permutation P belongs to the BPCL class.>