Publication
Journal of Computer and System Sciences
Paper

Superconcentrators of depth 2

View publication

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.

Date

01 Jan 1982

Publication

Journal of Computer and System Sciences

Authors

Topics

Share