Skip to main content

Research Repository

Advanced Search

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

Stewart, I.A.; Xiang, Y.

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


Y. Xiang


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


Stewart, I., & Xiang, Y. (2010). One-to-many node-disjoint paths in (n,k)-star graphs. Discrete Applied Mathematics, 158(1), 62-70.

Journal Article Type Article
Publication Date Jan 6, 2010
Deposit Date Oct 21, 2009
Publicly Available Date Nov 27, 2009
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 158
Issue 1
Pages 62-70
Keywords Interconnection networks, (n,k)-star graphs, Many-to-one node-disjoint paths.
Publisher URL


You might also like

Downloadable Citations