Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes

Ashir, Y.A.; Stewart, I.A.

Abstract

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.

Citation

Ashir, Y., & Stewart, I. (2002). Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes. SIAM Journal on Discrete Mathematics, 15(3), 317-328. https://doi.org/10.1137/s0895480196311183

• Journal Article Type: Article
• Publication Date: 2002
• Deposit Date: Oct 8, 2008
• Publicly Available Date: Oct 8, 2008
• Journal: SIAM Journal on Discrete Mathematics
• Print ISSN: 0895-4801
• Electronic ISSN: 1095-7146
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 15
• Issue: 3
• Pages: 317-328
• DOI: https://doi.org/10.1137/s0895480196311183
• Keywords: Interconnection networks, Fault-tolerance, NP-completeness.
• Public URL: https://durham-repository.worktribe.com/output/1597634
• Publisher URL: http://epubs.siam.org/SIDMA/volume-15/art_31118.html