• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Zhuang, Hongbin (Zhuang, Hongbin.) [1] | Li, Xiao-Yan (Li, Xiao-Yan.) [2] (Scholars:李小燕) | Wang, Dajin (Wang, Dajin.) [3] | Lin, Cheng-Kuan (Lin, Cheng-Kuan.) [4] | Zhao, Kun (Zhao, Kun.) [5]

Indexed by:

EI Scopus SCIE

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:

Alternating group graphs Embedding Fault-tolerance Interconnection networks Partitioned edge faults

Community:

  • [ 1 ] [Zhuang, Hongbin]Fuzhou Univ, Coll Comp & Data Sci, Fuzhou 350108, Peoples R China
  • [ 2 ] [Li, Xiao-Yan]Fuzhou Univ, Coll Comp & Data Sci, Fuzhou 350108, Peoples R China
  • [ 3 ] [Zhao, Kun]Fuzhou Univ, Coll Comp & Data Sci, Fuzhou 350108, Peoples R China
  • [ 4 ] [Wang, Dajin]Montclair State Univ, Dept Comp Sci, Montclair, NJ 07043 USA
  • [ 5 ] [Lin, Cheng-Kuan]Natl Yang Ming Chiao Tung Univ, Dept Comp Sci, Hsinchu 30010, Taiwan

Reprint 's Address:

  • [Li, Xiao-Yan]Fuzhou Univ, Coll Comp & Data Sci, Fuzhou 350108, Peoples R China;;

Show more details

Related Keywords:

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:

WoS CC 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

Online/Total:126/10050372
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1