1-1hit |
In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t1,...,tk} of k nodes in a k-connected graph G, find k node-disjoint paths s ti, 1 i k. We give an O(n2) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs Gn which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(Gn) + 1 for n 4,6 and at most d(Gn) + 2 for n = 4,6, where d(Gn) = 3(n-1)/2 is the diameter of Gn. d(Gn) + 1 and d(Gn) + 2 are also the lower bounds on the length of the paths for the above problem in Gn for n 4,6 and n = 4,6, respectively.