About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Superconcentrators of depth 2
Abstract
It is shown that every n-superconcentrator of depth 2 has size μ(n log n); that there exist n-superconcentrators of depth 2 and size O(n(log n)2); and that there exist n-superconcentrators on which the pebble game can be played in space S and time O( (n log n)2 S), for a wide range of values of S. © 1982.