Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

Y.A. Ashir



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.
Publisher URL http://epubs.siam.org/SIDMA/volume-15/art_31118.html

Files

Published Journal Article (218 Kb)
PDF

Copyright Statement
© 2002 Society for Industrial and Applied Mathematics.







You might also like



Downloadable Citations