Bipartite Representations of Permutations and Permutation Networks

Yoshihide IGARASHI  Shoji SAKURAZAWA  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E62   No.10   pp.649-655
Publication Date: 1979/10/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
Bipartite representations of permutations are introduced, and the relation between the representations and the actions of permutation networks devised by Waksman et al is investigated. As an example of the application of the bipartite representations, a lucid algorithm for setting-up a permutation network to produce a given permutation is shown. An algorithm for counting the number of configurations of the network that produce a given permutation is derived. The computing time complexity of the algorithm by a random access machine is O (2N/2+O(log2N)).