About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1992
Conference paper
Existence and construction of edge disjoint paths on expander graphs
Abstract
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.