Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes
Ashir, Y.A.; Stewart, I.A.
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.
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|
|Deposit Date||Oct 8, 2008|
|Publicly Available Date||Oct 8, 2008|
|Journal||SIAM Journal on Discrete Mathematics|
|Publisher||Society for Industrial and Applied Mathematics|
|Peer Reviewed||Peer Reviewed|
|Keywords||Interconnection networks, Fault-tolerance, NP-completeness.|
Published Journal Article
© 2002 Society for Industrial and Applied Mathematics.
You might also like
Using semidirect products of groups to build classes of interconnection networks
Variational networks of cube-connected cycles are recursive cubes of rings
INRFlow: An interconnection networks research flow-level simulation framework
The influence of datacenter usage on symmetry in datacenter network design