Publication details for Professor Iain StewartStewart, I.A. & Xiang, Y. (2010). One-to-many node-disjoint paths in (n,k)-star graphs. Discrete Applied Mathematics 158(1): 62-70.
- Publication type: Journal Article
- ISSN/ISBN: 0166-218X
- DOI: 10.1016/j.dam.2009.08.013
- Keywords: interconnection networks; (n,k)-star graphs; many-to-one node-disjoint paths
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We present an algorithm which given a source node and a set of n−1 target nodes in the (n,k)-star graph Sn,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(k2n2).