An efficient algorithm for k-pairwise node disjoint path problem in hypercubes

In this paper, we give an efficient algorithm for the following k-pairwise node disjoint path problem in n-dimensional hypercubes H_n: Given k=[n/2] pairs of 2k distinct nodes (s₁, t₁), ..., (s_k, t_k) in H_n, n⩾4, find k node disjoint paths s_i→t_i, 1⩽i⩽k. Our algorithm finds the k node disjoint paths in O(n² log* n) time which improves the previous result of O(n ² log n). The length of the paths constructed in our algorithm is at most n+[log n]+1 which improves the previous result of 2n as well. The result of this paper shows that the k-pair-diameter d ^P_[n/2](_Hn) of H_n satisfies d ^P_[n/2](H_n)⩽n+[log n]+1