Node-to-set disjoint paths problem in star graphs

Given a node s and a set T = {t(1), ..., t(k)} of k nodes in a k-connected graph, the node-to-set disjoint paths problem is to find k node-disjoint paths P-i : s --> t(i), 1 less than or equal to i less than or equal to k. In this paper, we give two O(n(2)) time algorithms for the node-to-set disjoint paths problem in n-dimensional star graphs G(n) which are (n - 1)-connected. We first give a simple algorithm which finds n - 1 node-disjoint paths of length at most d(G(n)) + 3, where d(G(n)) = right perpendicular3(n - 1)/2left perpendicular is the diameter of G(n). Then, we refine the algorithm to find n - 1 node-disjoint paths of length at most d(G(n)) + 2. A lower bound on the length of the paths for the above problem in G(n) is d(G(n)) + 1. (C) 1997 Published by Elsevier Science B.V.