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

We present an algorithm which given a source node and a set of n−1n−1 target nodes in the (n,k)(n,k)-star graph Sn,kSn,k, where all nodes are distinct, builds a collection of n−1n−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−76k−7, and the algorithm has time complexity O(k2n2)O(k2n2).