Halvers and expanders (switching)

1 January 1992

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 686-692
https://doi.org/10.1109/sfcs.1992.267782

Abstract

The authors investigate the asymptotic efficiency of certain combinatorial networks called halvers, which are basic building blocks of many parallel algorithms. They improve the efficiency of halvers in terms of their depth. The novelty is the use of combinatorial circuits whose basic units are k-sorter switches.

Keywords

SWITCHES
SORTING
PARALLEL ALGORITHMS
SWITCHING CIRCUITS
REGISTERS
BIPARTITE GRAPH
DELAY EFFECTS
BINARY TREES

This publication has 3 references indexed in Scilit:

Explicit expanders and the Ramanujan conjectures
Published by Association for Computing Machinery (ACM) ,1986
A new parallel sorting algorithm based upon min-mid-max operations
BIT Numerical Mathematics, 1984
Sorting inc logn parallel steps
Combinatorica, 1983

Cited by 7 articles