Publication details for Professor Iain StewartAshir, Y.A. & Stewart, I.A. (2002). Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes. SIAM Journal On Discrete Mathematics 15(3): 317-328.
- Publication type: Journal Article
- ISSN/ISBN: 0895-4801, 1095-7146
- DOI: 10.1137/S0895480196311183
- Keywords: Interconnection networks, Fault-tolerance, NP-completeness.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We consider the fault-tolerant capabilities of networks of processors whose underlying topology is that of the k-ary n-cube $Q_n^k$, where k > 2 and n > 1. In particular, given a copy of $Q_n^k$ where some of the inter-processor links may be faulty but where every processor is incident with at least two healthy links, we show that if the number of faults is at most 4n-5 then $Q_n^k$ still contains a Hamiltonian circuit; but that there are situations where the number of faults is 4n-4 (and every processor is incident with at least two healthy links) and no Hamiltonian circuit exists. We also remark that given a faulty $Q_n^k$, the problem of deciding whether there exists a Hamiltonian circuit is NP-complete.