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|
|Record Created:||21 Oct 2009 16:50|
|Last Modified:||03 Oct 2016 11:00|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|