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

Qian-Ping GU, Shietung PENG

Summary :

In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t₁,...,t_k} of k nodes in a k-connected graph G, find k node-disjoint paths s t_i, 1 i k. We give an O(n²) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs G_n which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(G_n) + 1 for n 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 bounds on the length of the paths for the above problem in G_n for n 4,6 and n = 4,6, respectively.

• Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.4 pp.425-433
• Publication Date: 1997/04/25
• Type of Manuscript: Special Section PAPER (Special Issue on Parallel and Distributed Supercomputing)

Authors

Qian-Ping GU
Shietung PENG

Keyword

algorithms,  interconnection networks,  node-disjoint paths,  star graphs