Given a graph G = (V, E) and a set of k 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 k paths so found is edge-disjoint. (For arbitrary graphs the problem is N P-complete, although it is in p if k is fixed.) We present a polynomial time randomized algorithm for finding edge-disjoint paths in the random regular graph G_(n,r), for sufficiently large r. (The graph is chosen first, then an adversary chooses the pairs of end-points.) We show that almost every G_(n,r) is such that all sets of k = Ω(n/log n) pairs of vertices can be joined. This is within a constant factor of the optimum.
展开▼
