Node-to-set disjoint paths problem in star graphs

✍ Scribed by Qian-Ping Gu; Shietung Peng

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 567 KB
• Volume: 62
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00059-8

✦ Synopsis

GivenanodesandasetZ'={t~,..., tk} of k nodes in a k-connected graph, the node-to-set disjoint paths problem is to find k node-disjoint paths pi : s -+ ti, 1 < i < k. In this paper, we give two O(n*) time algorithms for the node-to-set disjoint paths problem in n-dimensional star graphs G, which are (n -1 )-connected. We first give a simple algorithm which finds n -1 node-disjoint paths of length at most d(Gn) + 3, where d( G,) = [3(n -I)/21 is the diameter of G,. Then, we refine the algorithm to find n -1 node-disjoint paths of length at most d(G,) + 2. A lower bound on the length of the paths for the above problem in Gn is d( G,) + 1.