Profile

Publication details for Professor Iain Stewart

Stewart, 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 papers: academic
• 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
• View online: Online version
• Durham research online: DRO record

Author(s) from Durham

• Professor Iain Stewart

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)$.