Stewart, I. A. and Xiang, Y. (2010) 'One-to-many node-disjoint paths in (n,k)-star graphs.', Discrete applied mathematics., 158 (1). pp. 62-70.
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).
|Keywords:||Interconnection networks, (n,k)-star graphs, Many-to-one node-disjoint paths.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (146Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.dam.2009.08.013|
|Date accepted:||No date available|
|Date deposited:||27 November 2009|
|Date of first online publication:||January 2010|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|