References

1

S. N. Bhatt and F. T. Leighton. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences, 28(2):300-343, April 1984.

2

R. P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201-208, April 1974.

3

R. P. Brent and H. T. Kung. A regular layout for parallel adders. IEEE Transactions on Computers, C-31(3):260-264, March 1982.

4

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. American Mathematical Society, 23:493-507, 1952.

5

R. Cole and U. Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 206-219, May 1986.

6

A. K. Dewdney. Computer recreations. Scientific American, 252(6):18-29, June 1985.

7

M. J. Fischer and R. E. Ladner. Parallel prefix computation. Journal of the ACM, 27(4):831-838, October 1980.

8

A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 136-146, May 1986.

9

A. V. Goldberg and R. E. Tarjan. Solving minimum-cost flow problems by successive approximation. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 7-18, May 1987.

10

R. I. Greenberg and C. E. Leiserson. Randomized routing on fat-trees. In Silvio Micali, editor, Randomness and Computation. Volume 5 of Advances in Computing Research, pages 345-374. JAI Press, Greenwich, CT, 1989.

11

W. D. Hillis and G. L. Steele Jr. Data parallel algorithms. Communications of the ACM, 29(12):1170-1183, December 1986.

12

A. R. Karlin and E. Upfal. Parallel hashing -- an efficient implementation of shared memory. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 160-168, May 1986.

13

J. Kilian, July 1986. Personal communication.

14

D. E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, Reading, MA, second edition, 1973.

15

H. T. Kung and C. E. Leiserson. Systolic arrays (for VLSI). In I. S. Duff and G. W. Stewart, editors, Sparse Matrix Proceedings, pages 256-282. SIAM, 1978.

16

F. T. Leighton and A. L. Rosenberg. Three-dimensional circuit layouts. SIAM Journal on Computing, 15(3):793-813, August 1986.

17

C. E. Leiserson. Area-Efficient VLSI Computation. MIT Press, Cambridge, MA, 1983.

18

C. E. Leiserson. Fat-trees: universal networks for hardware-efficient supercomputing. IEEE Transactions on Computers, C-34(10):892-901, October 1985.

19

C. E. Leiserson and B. M. Maggs. Communication-efficient parallel graph algorithms. Technical Memo MIT/LCS/TM-318, MIT Laboratory for Computer Science, Cambridge, MA, December 1986.

20

R. J. Lipton and R. E. Tarjan. A planar separator theorem. SIAM Journal of Applied Mathematics, 36(2):177-189, April 1979.

21

B. M. Maggs. Locality in Parallel Computation. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 1989.

22

G. Miller and J. Reif. Parallel tree contraction and its application. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 478-489, October 1985.

23

Yu. Ofman. On the algorithmic complexity of discrete functions. Soviet Physics - Doklady, 7(7):589-591, 1963. English translation.

24

G. F. Pfister and V. A. Norton. `Hot spot' contention and combining in multistage interconnection networks. IEEE Transactions on Computers, C-34(10):943-948, October 1985.

25

Y. Shiloach and U. Vishkin. An parallel connectivity algorithm. Journal of Algorithms, 3:57-67, 1982.

26

R. E. Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, PA, 1983.

27

R. E. Tarjan and U. Vishkin. Finding biconnected components and computing tree functions in logarithmic parallel time. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pages 12-20. IEEE Computer Society Press, October 1984.

28

C. D. Thompson. A Complexity Theory for VLSI. PhD thesis, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, 1980.

29

L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350-361, May 1982.

30

J. C. Wyllie. The Complexity of Parallel Computations. PhD thesis, Cornell University, Ithaca, NY, August 1979.