Enabling high fault-tolerant embedding capability of alternating group graphs

The Hamiltonian path/cycle serves as a robust tool for transmitting messages within parallel and distributed systems. However, the prevalent device-intensive nature of these systems often leads to the occurrence of faults. Tackling the critical challenge of tolerating numerous faults when constructing Hamiltonian paths and cycles in these systems is of utmost significance. The alternating group graph AG_n is a suitable interconnection network for building parallel and distributed systems due to its outstanding topological properties. Many studies have been dedicated to the fault-tolerant embedding of Hamiltonian paths and cycles in AG_n, but they all fail to reach the desired level of fault-tolerance. In this paper, we aim to enhance the edge fault-tolerant embedding capability of AG_n by leveraging a newly emerged fault model, called the Partitioned Edge Fault (PEF) model. We prove the existence of Hamiltonian paths/cycles tolerating large-scale edge faults in AG_n under the PEF model. Additionally, we propose a fault-tolerant Hamiltonian path embedding algorithm for AG_n under the PEF model and validate its effectiveness through experiments. To gauge the significance of each missed edge, we conduct experimental calculations for the average path length of every edge along the Hamiltonian path produced by the proposed embedding algorithm. Furthermore, the fault-tolerance comparison and experimental analysis reveal that our results improve the fault-tolerant embedding capability of AG_n from a linear level to an exponential one. To our knowledge, this is the first time that a Hamiltonian path/cycle embedding approach is proposed and actually implemented for AG_n with large-scale edge faults.