For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Bipartite Representations of Permutations and Permutation Networks
Yoshihide IGARASHI Shoji SAKURAZAWA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1979/10/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages
Full Text: PDF>>
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)).