We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

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.

Item Type:Article
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
Publisher Web site:
Publisher statement:Electronic version of an article published as Journal of interconnection networks, 8, 3, 2007, pp. 253-284,, © World Scientific Publishing Company,
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