Existence and construction of edge disjoint paths on expander graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Existence and construction of edge disjoint paths on expander graphs

Full text

Pdf (837 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 140 - 149

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Andrei Z. Broder	DEC-SRC, 130 Lytton Ave, Palo Alto, CA
Alan M. Frieze	Department of Mathematics, Carnegie-Mellon University
Eli Upfal	IBM Almaden Research Center, San Jose, CA and Department of Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 42, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129712.129727 What is a DOI?

REFERENCES

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	N. Alon. The linear arboricity of graphs. Israel J. Math., 62:311-325, 1988.
	2	Noga Alon, A parallel algorithmic version of the Local Lemma, Proceedings of the 32nd annual symposium on Foundations of computer science, p.586-593, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185423]
	3	N. Alon. The strong chromatic number of of a graph. Random Struct. Alg., 3:1-8, 1992.
	4	N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
	5	J. Beck. An Algorithmic Approach to the Lov~sz Local Lemma I. Random Struct. Alg., 2:343-365, 1991.
	6	V. Chv~tal Probabilistic methods in graph theory in Stochastics and Optimization (F.Archetti and F.Maffioli Eds.), Annals of Operations Research, 1:171-182, 1984.
	7	P. ErdSs and L. Lov~sz. Problems and Results on 3-Chromatic Hypergraphs and Some Related Questions. In Infinite and Finite Sets, (A. Hajnal et. al. eds), Colloq. Math. Soc. J. Bolyai 11, North Holland, 1975, pp. 609-627.
	8	T.I. Fenner and A.M. Frieze. On the connectivity of random m-orientable graphs and digraphs. Combinatorica, 2:347-359, 1982.
	9	A. Frank and A. Gyarfas. How to orient the edges of a graph? Colloq. Math. Soc. J. Bolyai, 18:353-364, 1978.
	10	J. Friedman , J. Kahn , E. Szemerédi, On the second eigenvalue of random regular graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.587-598, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73063]
	11	W. Hoeffding. Probability inequalities for Sums of Bounded Random variables. In Journal of the American Statistical Association, 58:13-30, 1963.
	12	T. Leighton and B. Maggs. Expanders might be practical: Fast algorithms for routing around faults in multibutterflies. In Proceedings of the 30th Annum Symposium on Foundations of Computer Science, 264-274. IEEE, 1990.
	13	A. Lubotsky, R. Phillips, and P. Sarnak. Ramanujan graphs, Combinatorica, 8:261-277, 1988.
	14	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]
	15	J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, 1987.
	16	D. Peleg and E. Upfal. Construction Disjoint Paths on Expander Graphs. Combinatorica, 9:289-313, 1989.
	17	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]
	18	N.R.obertson and P.D.Seymour Graph minors- XIII: The disjoint paths problem, to appear
	19	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]

CITED BY 7

	Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Jon Kleinberg , Éva Tardos, Approximations for the disjoint paths problem in high-diameter planar networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.26-35, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	Andrei Z. Broder , Alan M. Frieze , Stephen Suen , Eli Upfal, An efficient algorithm for the vertex-disjoint paths problem in random graphs, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.261-268, January 28-30, 1996, Atlanta, Georgia, United States
	Andrei A. Broder , Alan M. Frieze , Stephen Suen , Eli Upfal, Optimal construction of edge-disjoint paths in random graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.603-612, January 23-25, 1994, Arlington, Virginia, United States
	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999
	N. Alon , F. R. K. Chung , R. L. Graham, Routing permutations on graphs via matchings, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.583-591, May 16-18, 1993, San Diego, California, United States