References

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. KOMLfOS, AND E. SZEMERfEDI, 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.