Static and dynamic path selection on expander graphs (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Static and dynamic path selection on expander graphs (preliminary version): a random walk approach

Full text

Pdf (1.15 MB)

Source

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

El Paso, Texas, United States

Pages: 531 - 539

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Andrei Z. Broder	Digital Systems Research Center, 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): 2, Downloads (12 Months): 22, 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/258533.258646 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, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	2	B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive on-line routing. In 3~th Annual Symposium on Foundations of Computer Sctence, pages 32-40, Palo Alto, California, 3-5 Nov. 1993. IEEE.
	3	B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In SSth Annual Symposium on Foundatwns of Computer Science, pages 412-423, Santa Fe, New Mexico, 20-22 Nov. 1994. IEEE.
	4	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Existence and Construction of Edge-Disjoint Pathson Expander Graphs, SIAM Journal on Computing, v.23 n.5, p.976-989, Oct. 1994 [doi>10.1137/S0097539792232021]
	5	P. ErdSs and L. Lov~sz. Problems and results on 3- chromatic hypergraphs and some related questions. In A. Hajnal et al., editors, Infinite and Finite Sets, volume 11 of Colloq. Math. Soc. J. Bolyai, pages 609-627. 1975.
	6	Anil Kamath , Omri Palmon , Serge Plotkin, Routing and admission control in general topology networks with Poisson arrivals, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 28-30, 1996, Atlanta, Georgia, United States
	7	J. Kleinberg , R. Rubinfeld, Short paths in expander graphs, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.86, October 14-16, 1996
	8	A. Lubotsky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261-277, 1988.
	9	F.P. Kelley. Blocking probabilities in large circuitswitching networks. Adv. Appl. Prob., 18:573-505, 1986.
	10	F.T. Leighton and S. Rao. Circuit switching: a multi-commodity flow based approach. Proc. of 9th International Parallel Processing Symposium, 1995.
	11	Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
	12	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]

CITED BY 7

	Chi-Jen Lu, A deterministic approximation algorithm for a minmax integer programming problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.663-668, January 17-19, 1999, Baltimore, Maryland, United States
	Michael Molloy , Bruce Reed, Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.524-529, May 24-26, 1998, Dallas, Texas, 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
	Artur Czumaj , Christian Scheideler, A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.38-47, May 21-23, 2000, Portland, Oregon, United States
	Artur Czumaj , Christian Scheideler, Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.30-39, January 09-11, 2000, San Francisco, California, United States
	Tom Leighton , Satish Rao , Aravind Srinivasan, New algorithmic aspects of the Local Lemma with applications to routing and partitioning, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.643-652, January 17-19, 1999, Baltimore, Maryland, United States
	Petr Kolman , Christian Scheideler, Simple on-line algorithms for the maximum disjoint paths problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.38-47, July 2001, Crete Island, Greece