Skip to main content

Research Repository

Advanced Search

Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links

Stewart, I.A.

Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links Thumbnail


Authors



Abstract

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.

Citation

Stewart, I. (2007). Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links. Journal of Interconnection Networks, 8(3), 253-284. https://doi.org/10.1142/s0219265907002016

Journal Article Type Article
Publication Date Sep 1, 2007
Deposit Date Jun 29, 2009
Publicly Available Date Aug 25, 2009
Journal Journal of Interconnection Networks
Print ISSN 0219-2659
Electronic ISSN 1793-6713
Publisher World Scientific Publishing
Peer Reviewed Peer Reviewed
Volume 8
Issue 3
Pages 253-284
DOI https://doi.org/10.1142/s0219265907002016
Keywords Interconnection networks, k-ary n-cubes; hypercubes, Fault-tolerance, Hamiltonian cycles, Distributed algorithms, Embeddings.
Publisher URL http://www.worldscinet.com/cgi-bin/details.cgi?id=pii:S0219265907002016&type=html

Files





You might also like



Downloadable Citations