NODE-TO-SET DISJOINT PATHS WITH OPTIMAL LENGTH IN STAR GRAPHS

In this paper, we consider the following node-to-set disjoint paths pr oblem: given a node s and a set T = {t(1),...,t(k)} of k nodes in a k- connected graph G, find k node-disjoint paths s --> t(i), 1 less than or equal to i less than or equal to k. We give an O(n(2)) time algorit hm for the node-to-set disjoint paths problem in n-dimensional star gr aphs G(n) which are (n - 1)-connected. The algorithm finds the n - 1 n ode-disjoint paths of length at most d((G)n) + 1 for n not equal 4, 6 and at most d(G(n)) + 2 for n = 4,6, where d(G(n)) = [3(n-1)/2] is the diameter of G(n). d(G(n)) + 1 and d(G(n)) + 2 are also the lower boun ds on the length of the paths for the above problem in G(n) for n not equal 4, 6 and n = 4, 6, respectively.