Stewart, I. A. (2007) 'Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links.', Journal of interconnection networks., 8 (3). pp. 253-284.
We derive a sequential algorithm Find-Ham-Cycle with the following property. On input: k and n (specifying the k-ary n-cube Q(n,k); F, a set of at most 2n-2 faulty links; and v, a node of Q(n,k), the algorithm outputs nodes v+ and v- such that if Find-Ham-Cycle is executed once for every node v of Q(n,k) then the node v+ (resp. v-) denotes the successor (resp. predecessor) node of v on a fixed Hamiltonian cycle in Q(n,k) in which no link is in F. Moreover, the algorithm Find-Ham-Cycle runs in time polynomial in n and log k. We also obtain a similar algorithm for an n-dimensional hypercube with at most n-2 faulty links. We use our algorithms to obtain distributed algorithms to embed Hamiltonian cycles k-ary n-cubes and hypercubes with faulty links; our hypercube algorithm improves on a recently-derived algorithm due to Leu and Kuo, and our k-ary n-cube algorithm is the first distributed algorithm for embedding a Hamiltonian cycle in a k-ary n-cube with faulty links.
|Additional Information:||An extended abstract of this paper appeared in: Proc. of 12th International Conference on Parallel and Distributed Systems (ICPADS 2006), IEEE Computer Society Press (2006) 308-318.|
|Keywords:||Interconnection networks, k-ary n-cubes; hypercubes, Fault-tolerance, Hamiltonian cycles, Distributed algorithms, Embeddings.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (184Kb)
|Publisher Web site:||http://dx.doi.org/10.1142/S0219265907002016|
|Publisher statement:||Electronic version of an article published as Journal of interconnection networks, 8, 3, 2007, pp. 253-284, http://dx.doi.org/10.1142/S0219265907002016, © World Scientific Publishing Company, http://www.worldscinet.com/join/join.shtml|
|Date accepted:||No date available|
|Date deposited:||25 August 2009|
|Date of first online publication:||September 2007|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|