Wide-Sense Nonblocking Networks
- 1 May 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 1 (2), 158-173
- https://doi.org/10.1137/0401018
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} )$.
Keywords
This publication has 16 references indexed in Scilit:
- A lower bound on strictly non-blocking networksCombinatorica, 1988
- Expanding graphs contain all small treesCombinatorica, 1987
- The complexity of testing whether a graph is a superconcentratorInformation Processing Letters, 1981
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- Blocking States in Connecting Networks Made of Square Switches Arranged in StagesBell System Technical Journal, 1981
- Semilattice Characterization of Nonblocking NetworksBell System Technical Journal, 1973
- Generalized multi‐stage connection networksNetworks, 1972
- On non‐blocking switching networksNetworks, 1971
- Heuristic Remarks and Mathematical Problems Regarding the Theory of Connecting SystemsBell System Technical Journal, 1962
- A Study of Non-Blocking Switching NetworksBell System Technical Journal, 1953