**1**-
W. A. AIELLO, F. T. LEIGHTON, B. M. MAGGS, AND M. NEWMAN,
*Fast algorithms for bit-serial routing on a hypercube*, Mathematical Systems Theory, 24 (1991), pp. 253-271. **2**-
M. AJTAI, J. KOMLf
OS, AND E. SZEMERf EDI, *Sorting in parallel steps*, Combinatorica, 3 (1983), pp. 1-19. **3**-
L. A. BASSALYGO AND M. S. PINSKER,
*Complexity of an optimum nonblocking switching network without reconnections*, Problems of Information Transmission, 9 (1974), pp. 64-66. **4**-
height 2pt depth -1.6pt width 23pt,
*Asymptotically optimal networks for generalized rearrangeable switching and generalized switching without rearrangement*, Problemy Peredachi Informatsii, 16 (1980), pp. 94-98. **5**-
B. BEIZER,
*The analysis and synthesis of signal switching networks*, in Proceedings of the Symposium on Mathematical Theory of Automata, Brooklyn, NY, 1962, Brooklyn Polytechnic Institute, pp. 563-576. **6**-
V. E. BENE\VS,
*Optimal rearrangeable multistage connecting networks*, Bell System Technical Journal, 43 (1964), pp. 1641-1656. **7**-
D. G. CANTOR,
*On construction of non-blocking switching networks*, in Proceedings of the Symposium on Computer Communication Networks and Teletraffic, Brooklyn, NY, 1972, Brooklyn Polytechnic Institute, pp. 253-255. **8**-
D. DOLEV, C. DWORK, N. PIPPENGER, AND A. WIDGERSON,
*Superconcentrators, generalizers and generalized connectors with limited depth*, in Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Apr. 1983, pp. 42-51. **9**-
P. FELDMAN, J. FRIEDMAN, AND N. PIPPENGER,
*Non-blocking networks*, in Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 1986, pp. 247-254. **10**-
height 2pt depth -1.6pt width 23pt,
*Wide-sense nonblocking networks*, SIAM Journal of Discrete Mathematics, 1 (1988), pp. 158-173. **11**-
J. FRIEDMAN,
*A lower bound on strictly non-blocking networks*, Combinatorica, 8 (1988), pp. 185-188. **12**-
A. V. GOLDBERG, B. M. MAGGS, AND S. A. PLOTKIN,
*A parallel algorithm for reconfiguring a multibutterfly network with faulty switches*, IEEE Transactions on Computers, 43 (1994), pp. 321-326. **13**-
N. KAHALE,
*Better expansion for Ramanujan graphs*, in Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Oct. 1991, pp. 398-404. **14**-
C. P. KRUSKAL AND M. SNIR,
*A unified theory of interconnection network structure*, Theoretical Computer Science, 48 (1986), pp. 75-94. **15**-
F. T. LEIGHTON,
*Parallel computation using meshes of trees*, in 1983 Workshop on Graph-Theoretic Concepts in Computer Science, Linz, 1984, Trauner Verlag, pp. 200-218. **16**-
height 2pt depth -1.6pt width 23pt,
*Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes*, Morgan Kaufmann, San Mateo, CA, 1992. **17**-
F. T. LEIGHTON AND B. M. MAGGS,
*Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks*, IEEE Transactions on Computers, 41 (1992), pp. 578-587. **18**-
T. LEIGHTON, C. E. LEISERSON, AND D. KRAVETS,
*Theory of parallel and VLSI computation*, Research Seminar Series Report MIT/LCS/RSS 8, MIT Laboratory for Computer Science, May 1990. **19**-
T. LEIGHTON, D. LISINSKI, AND B. MAGGS,
*Empirical evaluation of randomly-wired multistage networks*, in Proceedings of the 1990 IEEE International Conference on Computer Design: VLSI in Computers & Processors, IEEE Computer Society Press, Sept. 1990, pp. 380-385. **20**-
T. LEIGHTON AND G. PLAXTON,
*A (fairly) simple circuit that (usually) sorts*, in Proceedings of the 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Oct. 1990, pp. 264-274. **21**-
C. E. LEISERSON,
*Fat-trees: universal networks for hardware-efficient supercomputing*, IEEE Transactions on Computers, C-34 (1985), pp. 892-901. **22**-
G. LIN AND N. PIPPENGER,
*Parallel algorithms for routing in non-blocking networks*, in Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1991, pp. 272-277. **23**-
G. A. MARGULIS,
*Explicit constructions of concentrators*, Problems of Information Transmission, 9 (1973), pp. 325-332. **24**-
G. M. MASSON AND B. W. JORDAN, JR.,
*Generalized multi-stage connection networks*, Networks, 2 (1972), pp. 191-209. **25**-
D. NASSIMI AND S. SAHNI,
*Parallel permutation and sorting algorithms and a new generalized connection network*, Journal of the ACM, 29 (1982), pp. 642-667. **26**-
Y. P. OFMAN,
*A universal automaton*, Transactions of the Moscow Mathematical Society, 14 (1965), pp. 186-199. **27**-
D. PELEG AND E. UPFAL,
*Constructing disjoint paths on expander graphs*, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing, May 1987, pp. 264-273. **28**-
N. PIPPENGER,
*The complexity theory of switching networks*, PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1973. **29**-
height 2pt depth -1.6pt width 23pt,
*On rearrangeable and nonblocking switching networks*, Journal of Computer and System Sciences, 17 (1978), pp. 145-162. **30**-
height 2pt depth -1.6pt width 23pt,
*Telephone switching networks*, in Proceedings of Symposia in Applied Mathematics, vol. 26, 1982, pp. 101-133. **31**-
height 2pt depth -1.6pt width 23pt,
*Self-routing superconcentrators*, in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, May 1993, pp. 355-361. **32**-
N. PIPPENGER AND L. G. VALIANT,
*Shifting graphs and their applications*, Journal of the ACM, 23 (1976), pp. 423-432. **33**-
N. PIPPENGER AND A. C. YAO,
*Rearrangeable networks with limited depth*, SIAM Journal of Algebraic and Discrete Methods, 3 (1982), pp. 411-417. **34**-
J. H. REIF AND L. G. VALIANT,
*A logarithmic time sort for linear size networks*, Journal of the ACM, 34 (1987), pp. 60-76. **35**-
C. E. SHANNON,
*Memory requirements in a telephone exchange*, Bell System Technical Journal, 29 (1950), pp. 343-349. **36**-
J. S. TURNER,
*Practical wide-sense nonblocking generalized connectors*, Technical Report WUCS-88-29, Department of Computer Science, Washington University, St. Louis, MO, 1988. **37**-
E. UPFAL,
*An deterministic packet routing scheme*, in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 1989, pp. 241-250. **38**-
A. WAKSMAN,
*A permutation network*, Journal of the ACM, 15 (1968), pp. 159-163.

Mon Jul 22 21:19:59 EDT 1996