Indexed by:
Abstract:
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.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
ISSN: 0167-739X
Year: 2024
Volume: 158
Page: 110-121
6 . 2 0 0
JCR@2023
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: