Article

Free access

Edge-disjoint paths in expander graphs

Author:

Alan M. FriezeAuthors Info & Claims

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

Pages 717 - 725

Published: 01 February 2000 Publication History

PDF eReader

References

[1]

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland 197'6.]]

Digital Library

Google Scholar

[2]

A. Z. Broder, A. M. Frieze, and E. Upfal, Existence and construction of edge disjoint paths on expander graphs, SIAM Journal on Computing 23 (1994) 976-989.]]

Digital Library

Google Scholar

[3]

A. Z. Broder, A. M. Frieze, and E. Upfal, Existence and construction of edge low congestion paths on expander graphs, Random Structures and Algorithms 14 (1999) 87-109.]]

Digital Library

Google Scholar

[4]

I.H.Dinwoodie, A probability inequality for the occupation probability of a reversible Markov chain, The Annals of Applied Probability 5 (1995) 37-43.]]

Google Scholar

[5]

A.M.Frieze, Disjoint Paths in Expander Graphs via Random Walks: a Short Survey, Proceedings of Random '98, Lecture Notes in Computer Science 1518 (1998) Springer, 1-14.]]

Digital Library

Google Scholar

[6]

A.M.Frieze and M.Molloy, Splitting an expander graph, Journal of Algorithms 33 (1999) 166-172.]]

Digital Library

Google Scholar

[7]

A.M.Frieze and L.Zhao, Edge disjoint paths in random regular graphs, Proceedings of the 10th Annual ACM- SIAM Symposium on Discrete Algorithms (1999) 291- 299.]]

Digital Library

Google Scholar

[8]

D. Gale, A theorem on flows in networks, Pacific Journal of Mathematics 7 (1957) 1073-1082.]]

Google Scholar

[9]

D.Gillman, A Chernoff bound for random walks on expander graphs, SIAM Journal on Computing 27 (1998) 1203-1220.]]

Digital Library

Google Scholar

[10]

N.Kahale, Large deviation bounds for Markov chains, DIMACS Technical Report, DIMACS, Rutgers University, New Brunswick N J, 1994.]]

Google Scholar

[11]

J.Kleinberg and R.Rubinfeld, Short paths in expander graphs, Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, (1996) 86- 95.]]

Digital Library

Google Scholar

[12]

T.Leighton and S.Rao, Circuit switching: a multicommodity flow based approach, Proceedings of a Workshop on Randomized Parallel Computing 1996.]]

Google Scholar

[13]

T.Leighton, S.Rao and A.Srinivasan, Multi-commodity flow and circuit switching, Proceedings of the Hawaii International Conference on System Sciences, 1998.]]

Digital Library

Google Scholar

[14]

T.Leighton, S.Rao and A.Srinivasan, New algorithmic aspects of the local lemma with applications to partitioning and routing.]]

Google Scholar

[15]

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

Google Scholar

[16]

D. Peleg and E. Upfal, Constructing disjoint paths on expander graphs, Combinatorica 9, (1989) 289-313.]]

Google Scholar

[17]

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

Google Scholar

[18]

A. Sinclair and M. Jerrum, Approximate counting, uniform generation, and rapidly mixing Markov chains, Information and Computation 82 (1989) 93-133.]]

Digital Library

Google Scholar

Cited By

View all

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
Bansal NFriggstad ZKhandekar RSalavatipour M(2014)A logarithmic approximation for unsplittable flow on line graphsACM Transactions on Algorithms10.1145/253264510:1(1-15)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2532645

Index Terms

Edge-disjoint paths in expander graphs
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

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 ${\...
The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

We consider the following well-known problem, which is called the edge-disjoint paths problem.

Input: A graph G with n vertices and m edges, k pairs of vertices (s₁, t₁), (s₂, t₂),..., (s_k, t_k) in G.

Output: Edge-disjoint paths P₁, P₂,..., P_k in G such ...
Edge Disjoint Paths in Moderately Connected Graphs

We study the edge disjoint paths (EDP) problem in undirected graphs: Given a graph $G$ with $n$ nodes and a set $\mathcal{T}$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

February 2000

965 pages

ISBN:0898714532

Chairman:
David Shmoys

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 2000

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
369
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Bansal NFriggstad ZKhandekar RSalavatipour M(2014)A logarithmic approximation for unsplittable flow on line graphsACM Transactions on Algorithms10.1145/253264510:1(1-15)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2532645

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

The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

Edge Disjoint Paths in Moderately Connected Graphs