Node-to-Set Disjoint Paths with Optimal Length in Star Graphs

Qian-Ping GU  Shietung PENG  

IEICE TRANSACTIONS on Information and Systems   Vol.E80-D   No.4   pp.425-433
Publication Date: 1997/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Parallel and Distributed Supercomputing)
algorithms,  interconnection networks,  node-disjoint paths,  star graphs,  

Full Text: PDF(766.6KB)>>
Buy this Article

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.