Explicit constructions of linear-sized superconcentrators. (English) Zbl 0487.05045


05C40 Connectivity
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] Angluin, D., A note on a construction of margulis, Inform. process. lett., 8, 17-19, (1979) · Zbl 0398.94041
[3] Chung, F.R.K., On concentrators, superconcentrators, generalized, and nonblocking networks, Bell. sys. tech. J., 58, 1765-1777, (1978) · Zbl 0415.94021
[4] Gabber, O.; Galil, Z., Explicit constructions of linear size superconcentrators, (), 364-370
[5] Margulus, G.A., Explicit construction of concentrators, Problemy peredači informacii, 9, No. 4, 71-80, (1973), (English translation in Problems Inform. Transmission (1975))
[6] Pinsker, M.S., On the complexity of a concentrator, (), 318/1-318/4
[7] Pippenger, N., Superconcentrators, SIAM J. comput., 6, 298-304, (1972) · Zbl 0361.05035
[8] Schmidt, K., Asymptotically invariant sequences and an action of SL (2, Z), (1979), Math. Inst., University of Warwick Coventry, manuscript
[9] Valiant, L.G., On nonlinear lower bounds in computational complexity, (), 45-53 · Zbl 0489.68036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.