Scheideler C. Universal Routing Strategies for Interconnection Networks

232 References

[ST97] A. Srinivasan, C.-P. Teo. A constant-factor approximation algorithm for

packet routing, and balancing local vs. global criteria. In 29th Ann. ACM Syrup.

on Theory of Computing, 1997.

[Su94] T. Suel. Improved bounds for routing and sorting on multi-dimensional

meshes. In Proc. of the 6th Ann. ACM Syrup. on Parallel Algorithms and Ar-

chitectures, pp. 26-35, 1994.

[SV93] O. S~kora, I. V~o. Edge seperators for graphs of bounded genus with ap-

plications. Theoretical Computer Science 112, pp. 419-429, 1993.

[SV96] C. Scheideler, B. VScking. Universal continuous routing strategies. In Proe.

of the 8th Ann. ACId Syrup. on Parallel Algorithms and Architectures, pp. 142-

151, 1996.

[TK77] C.D. Thompson, H.T. Kung. Sorting on a mesh-connected parallel com-

puter. Communications of the ACM 20, pp. 263-271, 1977.

[TW91] A. Trew, G. Wilson. Past, Present, Parallel - A Survey of Available Par-

allel Computing Systems, Springer Verlag, 1991.

[Up82] E. Upfal. Efficient schemes for parallel communication. In Proc. of the 1st

Ann. ACId Syrup. on Principles of Distributed Computing, pp. 241-250, 1982.

[Up89] E. Upfal. An O(log N) deterministic packet routing scheme. In Proc. of the

21st Ann. ACM Syrup. on Theory of Computing, pp. 241-250, 1989.

[Up92] E. Upfal. An O(log N) deterministic packet routing scheme. Journal of the

ACM 39, pp. 55-70, 1992.

[UW87] E. Upfal, A. Wigderson. How to share memory in a distributed system.

Journal of the ACM 34, pp. 116-127, 1987.

[Va82] L.G. Valiant. A scheme for fast parallel communication. SIAM J. on Com-

puting 11(2), pp. 350-361, 1982.

[Va90] L.G. Valiant. A bridging model for parallel computation. Communications

of the ACM 33(8), pp. 103-111, 1990.

[Va94] V.V. Vazirani. A theory of alternating paths and blossoms for proving cor-

rectness of the O(~V/~IEI) general graph maximum matching algorithm. Com-

binatorica 14(1), pp. 71-109, 1994.

[Wa68] A. Waksman. A permutation network. Journal of the ACM 15(1), pp. 159-

163, 1968.

[Wi91] R.D. Williams. Performance of dynamic load balancing algorithms for un-

structured mesh calculations. Concurrency: Practice and Experience 3(5), pp.

457-481, 1991.

[ZA95] Z. Zhang, A.S. Acampora. A heuristic wavelength assignment algorithm

for multihop WDM networks with wavelength routing and wavelength re-use.

IEEE/ACM Trans. on Networking 3(3), pp. 281-288, 1995.