IEEE Transactions on Parallel and Distributed Systems · 2012 · 16 citations · 23 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsDirected Acyclic GraphsGraph AlgorithmsGraph TheoryHardware Fault ToleranceHypercube NetworksReliable System DesignCircuit Graph TheoryHamiltonian GraphsHypercube Network Fault Tolerance
A graph G is conditional k-edge-fault Hamiltonian if it remains Hamiltonian after deleting at most k edges and each vertex incident to at least two nonfaulty edges. A graph G is k-edge-fault Hamiltonian-connected if it remains Hamiltonian-connected after deleting at most k edges. This study shows that the conditional edge-fault Hamiltonicity of the Cartesian product network G x H can be efficiently evaluated given two graphs G and H that are edge-fault Hamilton-connected and conditional edge-fault Hamiltonian. This study uses the result to evaluate the conditional edge-fault Hamiltonicity of two multiprocessor systems, the generalized hypercubes and the nearest neighbor mesh hypercubes, both of which belong to Cartesian product networks.
23