Eli Upfal
Journal of the ACM
Given an expander graph G = (V, E) and a set of K disjoint pairs of vertices in V", we are interested in finding for each pair (ai,bi), a path connecting a,-to bi, such that the set of K paths so found is edge disjoint. (For general graphs the related decision problem is NP-complete.) We prove sufficient conditions for the existence of K ≤ n/(logn)κ edge disjoint paths connecting any set of K disjoint pairs of vertices on any n vertex bounded degree expander,where k depends only on the expansion properties of the input graph, and not on n. Furthermore, we present a randomized o(n3) time algorithm, and a random NC algorithm for constructing these paths. (Previous existence proofs and construction algorithms allowed only up to ne pairs, for some ∈ ≪ 1/3, and strong expanders [16].) In passing, we develop an algorithm for splitting a sufficiently strong expander into two edge disjoint spanning expanders.
Eli Upfal
Journal of the ACM
Cynthia Dwork, Orli Waarts
STOC 1992
Uriel Feige, László Lovász
STOC 1992
Eli Shamir, Eli Upfal
Journal of Parallel and Distributed Computing