AN EFFICIENT ALGORITHM FOR K-PAIRWISE DISJOINT PATHS IN STAR GRAPHS

In this paper, we give an efficient algorithm for the following proble m in the n-dimensional star graph G(n): Given k = inverted right perpe ndicular (n - 1)/2 inverted left perpendicular pairs of distinct nodes (s(1), t(1)), ..., (s(k), t(k)) in G(n), find k node-disjoint paths s (i) --> t(i), 1 less than or equal to i less than or equal to k. Our a lgorithm finds the k disjoint paths of length at most d(G(n)) + 5 in O (n(2)) optimal time, where d(G(n)) = right perpendicular 3(n - 1)/2 le ft perpendicular is the diameter of G(n). This improves the previous r esults of 4(n - 2) (path length) and O(n(4) logn) (time), respectively . (C) 1998 Published by Elsevier Science B.V. All rights reserved.