SOME GROUP THEORETIC RESULTS TOWARDS A LINEAR-TIME SET UP ALGORITHM FOR BENES NETWORKS.

An open problem about Benes networks deals with setting them up for a permutation in less than O(nlgn) steps. The paper considers the problem within the framework of group theory and provides results that may ultimately lead to a linear set up time for such networks. More specifically, we establish a firm relation between Benes networks, and coset and double coset decompositions of symmetric groups. This relation then leads to the elimination of some combinations of switch settings as possible solutions. We also discuss how these decompositions may be used to factor arbitrary permutations into the generic permutations of Benes networks.