An algorithm for the construction of concentrators from 2 x 2 sorters
Shou-Yen Li, Gar Koo, Hui Li · DIMACS series in discrete mathematics and theoretical computer science · 1998
This paper presents polynomial-time algorithms for the construction of deterministic and internally non-blocking concentrators from multi-stage cascades of 2x2 sorters. The approach is a generalization of "Fast Knockout" and "Sortout" techniques. The goal is to construct best known m-to-n networks of 2x2 sorters for m-to-n concentration, where m and n are within the practical range. The main criterion on the complexity of concentration is the number of stages in the cascade.