IEEE Transactions on Computers · 1993 · 85 citations · 4 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsComputational ComplexityHardware Fault ToleranceHypercube NetworksFault DiameterHypercube Network DiameterHypercube Network Fault ToleranceHypercube TopologyN-cube Networks
It is shown that the diameter of an n-dimensional hypercube can only increase by an additive constant of 1 when (n-1) faulty processors are present. Based on the concept of forbidden faulty sets, which guarantees the connectivity of the cube in the presence of up to (2n-3) faulty processors. It is shown that the diameter of the n-cube increases to (n-2) as a result of (2n-3) processor failures. It is also shown that only those nodes whose Hamming distance is (n-2) have the potential to be located at two ends of the diameter of the damaged cube. It is proven that all the n-cubes with (2n-3) faulty processors and a fault-diameter of (n+2) are isomorphic. A generalization to the subject study is presented.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
4
Topological properties of hypercubes
Yousef Saad, Martin H. Schultz · IEEE Transactions on Computers · 1988 · 1.4K citations