Assessing Embedding Capability of Arrangement Graphs From the Perspectives of Partitioned Edge Faults
- 17 October 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Reliability
- Vol. 74 (4) , 5753-5764
Abstract
The Hamiltonian path serves as a robust tool for unicast or multicast communication in parallel and distributed systems. Embedding this path structure into large-scale systems, especially those with numerous failures, remains a formidable and pressing challenge. The arrangement graph is a topology that not only generalizes many renowned network architectures but is also a promising framework for future computer systems. Extensive research has been conducted on the fault-tolerant embedding of Hamiltonian paths in the arrangement graph or its subclasses, yet these efforts have not attained the desired fault tolerance levels. In this article, we focus on significantly improving the edge fault-tolerant embedding capabilities of arrangement graphs by adopting a novel fault model, termed the partitioned edge fault model. We first prove the existence of Hamiltonian path avoiding large-scale edge faults in arrangement graphs. Then we develop a corresponding Hamiltonian path embedding algorithm with high fault-tolerant capability for arrangement graphs. Both theoretical comparisons and experimental analyses reveal that our methods yield significant enhancements in fault tolerance over existing studies. Furthermore, building upon the generated Hamiltonian path, we devise a dual-path multicast routing strategy and evaluate its latency performance.Keywords
Funding Information
- National Natural Science Foundation of China (62572124)
- National Natural Science Foundation of China (62002062)
- Natural Science Foundation of Fujian Province (2022J05029)
- Hong Kong Research Grants Council (11211422)
This publication has 41 references indexed in Scilit:
- CTWR: A congestion, temperature and wear-aware routing algorithm for partially-connected 3D network-on-chipComputers and Electrical Engineering, 2025
- Paired 2-disjoint path covers of balanced hypercube under the partitioned edge fault modelThe Journal of Supercomputing, 2024
- Enabling high fault-tolerant embedding capability of alternating group graphsFuture Generation Computer Systems, 2024
- Three edge-disjoint Hamiltonian cycles in crossed cubes with applications to fault-tolerant data broadcastingThe Journal of Supercomputing, 2022
- On exploiting priority relation graph for reliable multi-path communication in mobile social networksInformation Sciences, 2019
- Hamiltonian properties of honeycomb meshesInformation Sciences, 2013
- Embedding Hamiltonian cycles in alternating group graphs under conditional fault modelInformation Sciences, 2009
- Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faultsThe Journal of Supercomputing, 2008
- Edge-pancyclicity and path-embeddability of bijective connection graphsInformation Sciences, 2008
- Arrangement graphs: a class of generalized star graphsInformation Processing Letters, 1992