Ashir, Y. A. and Stewart, I. A. (2002) 'Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes.', SIAM journal on discrete mathematics., 15 (3). pp. 317-328.
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.
|Keywords:||Interconnection networks, Fault-tolerance, NP-completeness.|
|Full text:||PDF - Published Version (214Kb)|
|Publisher Web site:||http://dx.doi.org/10.1137/S0895480196311183|
|Publisher statement:||© 2002 Society for Industrial and Applied Mathematics.|
|Record Created:||08 Oct 2008|
|Last Modified:||14 Jun 2011 16:34|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|