Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AGRAWAL, A., KLEIN, P.N., AND RAVI, R. 1993. Cutting down on fill using nested dissection: Provably good elimination orderings. In Graph Theory and Sparse Matrix Computation, A. George, J. Gilbert, and J. W. H. Liu, eds. IMA Volumes in Mathematics and Its Applications, Springer- Verlag, New York, pp. 31-55.
	2	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States  [doi>10.1145/225058.225140]
	3	Yonatan Aumann , Yuval Rabani, Improved bounds for all optical routing, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 22-24, 1995, San Francisco, California, United States
	4	Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998  [doi>10.1137/S0097539794285983]
	5	Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SIAM Journal on Computing, v.28 n.1, p.263-277, Feb. 1999  [doi>10.1137/S0097539794271898]
	6	Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada  [doi>10.1145/195058.195238]
	7	AWERBUCH, B. AND PELEG, D. 1990. Sparse partitions. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 503-513.
	8	András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n2) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States  [doi>10.1145/237814.237827]
	9	BHATT, S. N. AND LEIGHTON, F.T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 2, 300-343.
	10	Hans L. Bodlaender , John R. Gilbert , Hjálmtýr Hafsteinsson , Ton Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, v.18 n.2, p.238-255, March 1995  [doi>10.1006/jagm.1995.1009 ]
	11	BOURGAIN, J.1985. On Lipschitz embedding of finite metric spaces in Hilbert space. Is. J. Math. 52, 46 -52.
	12	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Existence and construction of edge disjoint paths on expander graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1992, Victoria, British Columbia, Canada  [doi>10.1145/129712.129727]
	13	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Static and dynamic path selection on expander graphs (preliminary version): a random walk approach, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.531-539, May 04-06, 1997, El Paso, Texas, United States  [doi>10.1145/258533.258646]
	14	F. R. K. Chung , E.G. Coffman, Jr. , M.I. Reiman , B. Simon, The forwarding index of communication networks, IEEE Transactions on Information Theory, v.33 n.2, p.224-232, March 1987  [doi>10.1109/TIT.1987.1057290]
	15	CHVATAL, V. 1983. Linear Programming. Freeman, San Francisco, Calif.
	16	COHEN, E. 1993. Fast algorithms for constructing t-spanners and paths with stretch t. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science (Nov.), IEEE Computer Society Press, Los Alamitos, Calif., pp. 648-658.
	17	DIACONIS, P. AND STROOCK, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36-61.
	18	DOLEV, D., LEIGHTON, F. T., AND TRICKEY, H. 1983. Planar embeddings of planar graphs. Tech. rep. HIT, Cambridge, Mass.
	19	J. A. Ellis , I. H. Sudborough , J. S. Turner, The vertex separation and search number of a graph, Information and Computation, v.113 n.1, p.50-79, Aug. 15, 1994  [doi>10.1006/inco.1994.1064 ]
	20	G. Even , J. Naor , S. Rao , B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.62, October 23-25, 1995
	21	Guy Even , Joseph (Seffi) Naor , Satish Rao , Baruch Schieber, Fast approximate graph partitioning algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 05-07, 1997, New Orleans, Louisiana, United States
	22	EVEN, G., NAOR, J., SCHIEBER, B., AND SUDAN, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 2, 151-174.
	23	FORD, L.R. AND FULKERSON, D.R. 1956. Sur le probldme des courbes gauches en topologie. Canad. J. Math 8, 399-404.
	24	FRANK, A. 1990. Packing paths, circuits and cuts--A survey. In Paths, Flows, and VLSI-Layout, B. Korte, L. Lovfisz, H.J. Pr6mel, and A. Schrijver, eds. Springer-Verlag, Berlin, Germany, pp. 47-100.
	25	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	26	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996  [doi>10.1137/S0097539793243016]
	27	HANSEN, M. 1989. Approximation algorithms for geometric embeddings in the plane and applications to parallel processing problems. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (Oct.). IEEE Computer Science Society Press, Los Alamitos, Calif., pp. 604-609.
	28	M. C. Heydemann , J.c. Meyer , D. Sotteau, On forwarding indices of networks, Discrete Applied Mathematics, v.23 n.2, p.103-123, May 1989  [doi>10.1016/0166-218X(89)90022-X ]
	29	M. C. Heydemann , J. C. Meyer , J. Opatrny , D. Sotteau, Forwarding indices of k-connected graphs, Discrete Applied Mathematics, 37-38, p.287-296, July 15, 1992  [doi>10.1016/0166-218X(92)90140-6 ]
	30	HEYDEMANN, M.C., MEYER, J.C., AND SOTTEAU, D. 1994. Forwarding indices of consistent routings and their complexity. Networks 24, 75-82.
	31	Hu, T.C. 1963. Multicommodity network flows. Oper. Res. 11, 3, 344-360.
	32	IRI, M. 1967. On an extension of the maximum-flow minimum cut theorem to multicommodity flows. J. Oper. Res. Soc. Japan 5, 4 (Dec.), 697-703.
	33	Anil Kamath , Omri Palmon, Improved interior point algorithms for exact and approximate solution of multicommodity flow problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.502-511, January 22-24, 1995, San Francisco, California, United States
	34	M Kirousis , C H Papadimitriou, Searching and pebbling, Theoretical Computer Science, v.47 n.2, p.205-218, Nov. 1986
	35	KLEIN, P., AGRAWAL, A., RAO, S., AND RAVI, R. 1989. Approximation through multicommodity flow. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (Oct.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 726-737.
	36	Philip N. Klein , Serge A. Plotkin , Satish Rao , Éva Tardos, Approximation algorithms for Steiner and directed multicuts, Journal of Algorithms, v.22 n.2, p.241-269, Feb. 1997  [doi>10.1006/jagm.1996.0833 ]
	37	Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994  [doi>10.1137/S0097539792241175]
	38	KLEIN, P., RAO, S., AGRAWAL, A., AND RAVI, R. 1995. Approximation through multicommodity flow. Combinatorica 15, 187-202.
	39	Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167261]
	40	KLEIN, P. N., BORGER, J. M., AND KANG, S. 1991. Approximating concurrent flow with uniform demands and capacities: An implementation. In Proceedings of DIMACS Implementation Challenge Workshop: Network Flows and Matching (Oct.). AMS, Providence, R.I., pp. 371-386.
	41	Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
	42	Frank Thomson Leighton, Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks, MIT Press, Cambridge, MA, 1983
	43	LEIGHTON, F.T., MAGGS, B., AND RAO, S. 1994. Packet routing and job-shop scheduling in o(congestion + dilation) steps. Combinatorica 14, 2, 167-180.
	44	LEIGHTON, F. T. AND RAO, S. 1996. Circuit switching: A multicommodity flow based approach. In Proceedings of the 1st Workshop on Randomized Parallel Computing (Apr.).
	45	Tom Leighton , Satish Rao , Aravind Srinivasan, Multicommodity Flow and Circuit Switching, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.459, January 06-09, 1998  [doi>10.1109/HICSS.1998.649241]
	46	LEIGHTON, F.T. AND RAO, S. 1988. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 256-269.
	47	Tom Leighton , Fillia Makedon , Serge Plotkin , Clifford Stein , Éva Tardos , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Journal of Computer and System Sciences, v.50 n.2, p.228-243, April 1995
	48	LEIGHTON, F.T., MAKEDON, F., AND TRAGOUDAS, S. 1990. Approximation algorithms for VLSI partition problems. In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, Calif.
	49	T. Leighton , B. Maggs, Fast algorithms for finding O(congestion+dilation) packet routing schedules, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.555, January 04-07, 1995
	50	LEIGHTON, f., MAGGS, B., AND RICHA, A. 1995. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Tech. Rep. School of Computer Science, Carnegie Mellon University, Pittsburgh, Pa.
	51	LEISERSON, C.E. 1980. Area-efficient layouts (for VLSI). In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (Oct.). IEEE Computer Science Press, Los Alimatos, Calif., pp. 270-281.
	52	LEONG, f., SHOR, P., AND STEIN, C. 1991. Implementation of a combinatorial multicommodity flow algorithm. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science: Volume 12, Network Flows and Matching, D. S. Johnson and C. C. McGeoch, eds. (Oct.). AMS, Providence R.I., pp. 387-406.
	53	LINIAL, N., LONDON, E., AND RABINOVICH, f. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215-245.
	54	LIPTON, J. AND TARJAN, R.E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 2 (Apr.), 177-189.
	55	LOMONOSOV, M.V. 1985. Combinatorial approaches to multiflow problems. Disc. Appl. Math. 11, 1-94.
	56	Lov#.sz, L. 1991. Random walk on graphs: A survey. Tech. Rep. Dept. Computer Science, Yale Univ., New Haven, Conn.
	57	MARGULIS, G.A. 1973. Explicit constructions of concentrators. Prob. Inf. Trans. 9, 325-332.
	58	MATULA, D. W. AND SHAHROKHI, F. 1986. The maximum concurrent flow problem and sparsest cuts. Tech. Rep. Southern Methodist Univ., Dallas, Tex.
	59	OKAMURA, H. AND SEYMOUR, P.D. 1981. Multicommodity flows in planar graphs. J. Combin. Theory, Ser. B 31, 75-81.
	60	PAPERNOV, B.A. 1990. Feasibility of multicommodity flows (in Russian). In Studies in Discrete Optimization, A. A. Friedman, ed. New York, pp. 17-34.
	61	James K. Park , Cynthia A. Phillips, Finding minimum-quotient cuts in planar graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.766-775, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167284]
	62	David Peleg , Eli Upfal, The token distribution problem, SIAM Journal on Computing, v.18 n.2, p.229-243, April 1989  [doi>10.1137/0218015]
	63	Serge A. Plotkin , Éva Tardos, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.691-697, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167263]
	64	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988  [doi>10.1016/0022-0000(88)90003-7]
	65	Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada  [doi>10.1145/195058.195119]
	66	Satish B. Rao, Faster algorithms for finding small edge cuts in planar graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.229-240, May 04-06, 1992, Victoria, British Columbia, Canada  [doi>10.1145/129712.129735]
	67	R. Ravi , Ajit Agrawal , Philip Klein, Ordering problems approximated: single-processor scheduling and interval graph completion, Proceedings of the 18th international colloquium on Automata, languages and programming, p.751-762, June 1991, Madrid, Spain
	68	SCHRIJVER, A. 1990. Homotopic routing methods. In Paths, Flows, and VLSI-Layout, B. Korte, L. Lovfisz, H. J. Pr6mel, and A. Schrijver, eds. Springer-Verlag, Berlin, Germany, pp. 329-371.
	69	SEYMOUR, P.D. 1995. Packing directed circuits fractionally. Combinatorica 15, 281-288.
	70	Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990  [doi>10.1145/77600.77620]
	71	David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	72	SINCLAIR, A. 1991. Improved bounds for mixing rates of Markov chains and multicommodity flow. Tech. Rep. Laboratory for Foundations of Computer Science, Department of Computer Science, The University of Edinburgh, Edinburgh, Scotland.
	73	Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
	74	Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989  [doi>10.1016/0890-5401(89)90067-9]
	75	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	76	Spyros Tragoudas, VLSI partitioning approximation algorithms based on multicommodity flow and other techniques, University of Texas at Dallas, Richardson, TX, 1991
	77	VAIDYA, P.M. 1989. Speeding up linear programming using fast matrix multiplication. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, pp. 332-337.
	78	VALIANT, k.1981. Universality considerations in VLSI circuits. IEEE Trans. Comput. C-30, 2, 135-140.
	79	Ching-Wei Yeh , Chung-Kuan Cheng , Ting-Ting Y. Lin, A probabilistic multicommodity-flow solution to circuit clustering problems, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.428-431, November 1992, Santa Clara, California, United States

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski