We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

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:PDF - Accepted Version (184Kb)
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,
Record Created:29 Jun 2009 15:50
Last Modified:10 Nov 2011 11:11

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library