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

Stewart, I.A.; Xiang, Y.

doi:10.1016/j.dam.2009.08.013

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

Stewart, I.A.; Xiang, Y.

Authors

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

Y. Xiang

Abstract

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

Citation

Stewart, I., & Xiang, Y. (2010). One-to-many node-disjoint paths in (n,k)-star graphs. Discrete Applied Mathematics, 158(1), 62-70. https://doi.org/10.1016/j.dam.2009.08.013

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
DOI	https://doi.org/10.1016/j.dam.2009.08.013
Keywords	Interconnection networks, (n,k)-star graphs, Many-to-one node-disjoint paths.
Publisher URL	http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYW-4X962P9-2-C&_cdi=5629&_user=121711&_orig=search&_coverDate=01%2F06%2F2010&_sk=998419998&view=c&wchp=dGLbVtb-zSkWb&md5=be79741aa626ea15a1c781be3bb64df2&ie=/sdarticle.pdf