Wide-Sense Nonblocking Networks

Authors

Paul Feldman, Massachusetts Institute of Technology
Joel Friedman, Princeton University
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1988

Abstract

A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size O( n log n ), and with depth k and size O( n^{1 + 1/k} ( log n )^{1 - 1/k} ).

Rights Information

© 1988 Society for Industrial and Applied Mathematics

Recommended Citation

Paul Feldman, Joel Friedman, and Nicholas Pippenger. "Wide-Sense Nonblocking Networks", Society for Industrial and Applied Mathematics Journal of Discrete Mathematics, 1, 158 (1988).