1. Novel schemes for embedding Hamiltonian paths and cycles in balanced hypercubes with exponential faulty edges.
- Author
-
Li, Xiao-Yan, Zhao, Kun, Zhuang, Hongbin, and Jia, Xiaohua
- Subjects
- *
HYPERCUBES , *FAULT tolerance (Engineering) , *COMPUTER systems , *PARALLEL programming , *NETWORK performance - Abstract
The balanced hypercube B H n plays an essential role in large-scale parallel and distributed computing systems. With the increasing probability of edge faults in large-scale networks and the widespread applications of Hamiltonian paths and cycles, it is especially essential to study the fault tolerance of networks in the presence of Hamiltonian paths and cycles. However, existing researches on edge faults ignore that it is almost impossible for all faulty edges to be concentrated in a certain dimension. Thus, the fault tolerance performance of interconnection networks is severely underestimated. This paper focuses on three measures, t -partition-edge fault-tolerant Hamiltonian, t -partition-edge fault-tolerant Hamiltonian laceable, and t -partition-edge fault-tolerant strongly Hamiltonian laceable, and utilizes these measures to explore the existence of Hamiltonian paths and cycles in balanced hypercubes with exponentially faulty edges. We show that the B H n is 2 n − 1 -partition-edge fault-tolerant Hamiltonian laceable, 2 n − 1 -partition-edge fault-tolerant Hamiltonian, and (2 n − 1 − 1) -partition-edge fault-tolerant strongly Hamiltonian laceable for n ≥ 2. Comparison results show the partitioned fault model can provide the exponential fault tolerance as the value of the dimension n grows. • Based on the partitioned fault model, this paper propose three novel indicators for the balanced hypercubes B H n. • B H n is 2 n − 1 (resp. 2 n − 1 − 1)-partition-edge fault-tolerant (resp. strongly) Hamiltonian laceable. • Comparison results show the partitioned fault model can provide exponential fault tolerance as the dimension n grows. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF