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:||(VoR) Version of Record|
Download PDF (214Kb)
|Publisher Web site:||http://dx.doi.org/10.1137/S0895480196311183|
|Publisher statement:||© 2002 Society for Industrial and Applied Mathematics.|
|Date accepted:||No date available|
|Date deposited:||08 October 2008|
|Date of first online publication:||January 2002|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|