Article

Free access

Existence and construction of edge disjoint paths on expander graphs

Authors:

Andrei Z. Broder,

Alan M. Frieze,

Eli UpfalAuthors Info & Claims

STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

Pages 140 - 149

https://doi.org/10.1145/129712.129727

Published: 01 July 1992 Publication History

PDF eReader

References

[1]

N. Alon. The linear arboricity of graphs. Israel J. Math., 62:311-325, 1988.

Crossref

Google Scholar

[2]

N. Alon. A parallel algorithmic version of the Local Lemma. Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto ltico, 1991.

Digital Library

Google Scholar

[3]

N. Alon. The strong chromatic number of of a graph. Random Struct. Alg., 3:1-8, 1992.

Digital Library

Google Scholar

[4]

N. Alon and F.I#.K. Chung. Explicit construction of linear sized tolerant networks. Discrete Mathematics, 72:15-19, 1989.

Digital Library

Google Scholar

[5]

J. Beck. An Algorithmic Approach to the Lov~sz Local Lemma I. Random Struct. Alg., 2:343-365, 1991.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[8]

T.I. Fenner and A.M. Frieze. On the connectivity of random m-orientable graphs and digraphs. Combinatorica, 2:347-359, 1982.

Crossref

Google Scholar

[9]

A. Frank and A. Gyarfas. How to orient the edges of a graph? Colloq. Math. Soc. J. Bolyai, 18:353-364, 1978.

Google Scholar

[10]

J. Friedman, J. Kahn, and E. Szemer6di. On the second eigenvalue in random regular graphs. In Proceedings of the 21sth Annual ACM Symposium on Theory of Computing, pages 587-598, 1989.

Digital Library

Google Scholar

[11]

W. Hoeffding. Probability inequalities for Sums of Bounded Random variables. In Journal of the American Statistical Association, 58:13-30, 1963.

Crossref

Google Scholar

[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.

Google Scholar

[13]

A. Lubotsky, R. Phillips, and P. Sarnak. Ramanujan graphs, Combinatorica, 8:261-277, 1988.

Crossref

Google Scholar

[14]

A.Sinclair and M.Jerrum Approximate Counting, Uniform Generation, and Rapidly Mixing Markov Chains. Information and Computation, 82:93-133, 1989.

Digital Library

Google Scholar

[15]

J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, 1987.

Google Scholar

[16]

D. Peleg and E. Upfal. Construction Disjoint Paths on Expander Graphs. Combinatorica, 9:289-313, 1989.

Crossref

Google Scholar

[17]

D. Peleg and E. Upfal. The token distribution problem. SIAM Journal of Computing, 18:229-243, 1989.

Digital Library

Google Scholar

[18]

N.R.obertson and P.D.Seymour Graph minors- XIII: The disjoint paths problem, to appear

Google Scholar

[19]

E. Upfal. An O(logN) deterministic packet routing scheme, in Proceedings of #lst Annual A CM Symposium on Theory of Computing, 241-250, 1989.

Digital Library

Google Scholar

Cited By

View all

Bravyi SSharma YSzegedy MWolf R(2024) Generating EPR-pairs from an -party resource state Quantum10.22331/q-2024-05-14-13488(1348)Online publication date: 14-May-2024
https://doi.org/10.22331/q-2024-05-14-1348
Chuzhoy JKim DNimavat RDiakonikolas IKempe DHenzinger M(2018)Almost polynomial hardness of node-disjoint paths in gridsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188772(1220-1233)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188772
Coja-Oghlan AFeige UKrivelevich MReichman DIndyk P(2015)Contagious sets in expandersProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722260(1953-1987)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722260
Show More Cited By

Index Terms

Existence and construction of edge disjoint paths on expander graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
  2. Models of computation
    1. Abstract machines

Recommendations

Edge-Disjoint Paths in Expander Graphs

Given a graph G=(V,E)and a set of $\kappa$ pairs of vertices in V, we are interested in finding, for each pair (a_i, b_i), a path connecting a_i to b_i such that the set of $\kappa$ paths so found is edge-disjoint. For arbitrary graphs the problem is ${\...
Optimal Construction of Edge-Disjoint Paths in Random Graphs

Given a graph G=(V,E) with n vertices, m edges, and a family of $\kappa$ pairs of vertices in V, we are interested in finding for each pair (a_i, b_i) a path connecting a_i to b_i such that the set of $\kappa$ paths so found is edge disjoint. (For arbitrary ...
Existence and Construction of Edge-Disjoint Pathson Expander Graphs

Given an expander graph $G=(V,E)$ and a set of $q$ disjoint pairs of vertices in $V$, the authors are interested in finding for each pair $(a_i, b_i)$ a path connecting $a_i$ to $b_i$ such that the set of $q$ paths so found is edge disjoint. (For ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

July 1992

794 pages

ISBN:0897915119

DOI:10.1145/129712

Chairmen:
Rao Kosaraju
Johns Hopkins Univ., Baltimore, MD
,
Mike Fellows
Univ. of Victoria, Victoria, BC, Canada
,
Avi Wigderson
Hebrew University; Princeton Univ., Princeton, NJ
,
John Ellis
Univ. of Victoria, Victoria, BC, Canada

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC92

Sponsor:

SIGACT

STOC92: 24th Annual ACM Symposium on the Theory of Computing 1992

May 4 - 6, 1992

British Columbia, Victoria, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
518
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bravyi SSharma YSzegedy MWolf R(2024) Generating EPR-pairs from an -party resource state Quantum10.22331/q-2024-05-14-13488(1348)Online publication date: 14-May-2024
https://doi.org/10.22331/q-2024-05-14-1348
Chuzhoy JKim DNimavat RDiakonikolas IKempe DHenzinger M(2018)Almost polynomial hardness of node-disjoint paths in gridsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188772(1220-1233)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188772
Coja-Oghlan AFeige UKrivelevich MReichman DIndyk P(2015)Contagious sets in expandersProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722260(1953-1987)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722260
Srivastav A(2005)The lovász-local-lemma and schedulingEfficient Approximation and Online Algorithms10.5555/2168139.2168151(321-347)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/2168139.2168151
Bouganis ACaragiannis IKaklamanis C(2001)Implementation Issues and Experimental Study of a Wavelength Routing Algorithm for Irregular All-Optical NetworksAlgorithm Engineering10.1007/3-540-48318-7_21(258-270)Online publication date: 27-Jul-2001
https://doi.org/10.1007/3-540-48318-7_21
Broder AFrieze ASuen SUpfal ETardos É(1996)An efficient algorithm for the vertex-disjoint paths problem in random graphsProceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/313852.314072(261-268)Online publication date: 28-Jan-1996
https://dl.acm.org/doi/10.5555/313852.314072
Cypher RMeyer auf der Heide FScheideler CVöcking BMiller G(1996)Universal algorithms for store-and-forward and wormhole routingProceedings of the twenty-eighth annual ACM symposium on Theory of Computing10.1145/237814.237982(356-365)Online publication date: 1-Jul-1996
https://dl.acm.org/doi/10.1145/237814.237982
Kleinberg JTardos ÉLeighton FBorodin A(1995)Approximations for the disjoint paths problem in high-diameter planar networksProceedings of the twenty-seventh annual ACM symposium on Theory of computing10.1145/225058.225075(26-35)Online publication date: 29-May-1995
https://dl.acm.org/doi/10.1145/225058.225075
Broder AFrieze ASuen SUpfal ESleator D(1994)Optimal construction of edge-disjoint paths in random graphsProceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/314464.314659(603-612)Online publication date: 23-Jan-1994
https://dl.acm.org/doi/10.5555/314464.314659
Raghavan PUpfal ELeighton FGoodrich M(1994)Efficient routing in all-optical networksProceedings of the twenty-sixth annual ACM symposium on Theory of Computing10.1145/195058.195119(134-143)Online publication date: 23-May-1994
https://dl.acm.org/doi/10.1145/195058.195119
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Edge-Disjoint Paths in Expander Graphs

Optimal Construction of Edge-Disjoint Paths in Random Graphs

Existence and Construction of Edge-Disjoint Pathson Expander Graphs