Some Combinatorial Problems on a Permutation Network

Shoji SAKURAZAWA  Yoshihide IGARASHI  Yukio SHIBATA  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E64   No.6   pp.419-425
Publication Date: 1981/06/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
In this paper we discuss some combinatorial problems related to the permutation network devised by Waksman et al. NUM(π) means the number of configurations of the permutation network producing a permutation π. The main result in this paper is that 23N-5-(log2N(log2N+1))/2 is a lower bound on the number of elements in the set {ππ is a permutation on {1, , N} and NUM(π)1}. This is a remarkable improvement on the previous best lower bound 22N-3+(log2N(log2N-3))/2 given by Opferman and Tsao-Wu.