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

Stewart, I.A.; Xiang, Y.

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
• Electronic ISSN: 1872-6771
• 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.
• Public URL: https://durham-repository.worktribe.com/output/1565200
• 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