One-to-many node-disjoint paths in (n,k)-star graphs.

Abstract

We present an algorithm which given a source node and a set of $n-1$ target nodes in the $(n,k)$-star graph $S_{n,k}$, where all nodes are distinct, builds a collection of $n-1$ node-disjoint paths, one from each target node to the source. The collection of paths output from the algorithm is such that each path has length at most $6k-7$, and the algorithm has time complexity $O(k^2n^2)$.