An efficient algorithm for the k-pairwise disjoint paths problem in hypercubes

A graph G(V, E) (/V/ greater than or equal to 2k) satisfies property A(k) i f given k pairs of distinct nodes (s(1), t(1)),..., (s(k), t(k)) of V(G), t here are k mutually node-disjoint paths, one connecting s(i) and t(i) for e ach i. 1 less than or equal to i less than or equal to k. A necessary condi tion for any graph to satisfy A(k) is that it is (2k - 1)-connected. Hyperc ubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension ir ( which are n-connected) satisfy A([n/2]). In this paper we give an algorithm which, given k = ([n/2]) pairs of distinct nodes (s(1), t(1)),..., (s(k), t(k)) in the n-dimensional hypercube, finds the k disjoint paths of length at most n + [log n] + 1 in O(n(2) log* n) time. (C) 2000 Academic Press.