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

author:

Zhao, Kun (Zhao, Kun.) [1] | Zhuang, Hongbin (Zhuang, Hongbin.) [2] | Li, Xiao-Yan (Li, Xiao-Yan.) [3] (Scholars:李小燕) | Song, Fangying (Song, Fangying.) [4] (Scholars:宋方应) | Su, Lichao (Su, Lichao.) [5] (Scholars:苏立超)

Indexed by:

EI

Abstract:

The pancake graph is an interconnection network that plays a vital role in designing parallel and distributed systems. Due to the unavoidable occurrence of edge faults in large-scale networks and the wide application of path and cycle structures, it is essential and practical to explore the embedding of Hamiltonian paths and cycles in faulty networks. However, existing fault models ignore practical distributions of faulty edges so that only linear edge faults can be tolerated. This paper introduces a powerful fault model named the partitioned fault model. Based on this model, we study the existence of Hamiltonian paths and cycles on pancake graphs with large-scale faulty edges for the first time. We show that the n-dimensional pancake graph Pn admits a Hamiltonian path between any two vertices, avoiding ∑i=4n((i-4)((i-2)!-2)-1)+1 partition-edge faults for 4 ≤ n≤ 7, and avoiding ∑i=8n((i-1)!2-1)+399 faulty partition-edges for n≥ 8. Moreover, we prove that Pn admits a Hamiltonian cycle, avoiding ∑i=4n((i-4)((i-2)!-2)-1)+2 faulty partition-edges for 4 ≤ n≤ 7, and avoiding ∑i=8n((i-1)!2-1)+400 partition-edge faults for n≥ 8. The comparison results show that our results are a large-scale enhancement of existing results. © 2022, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

Keyword:

Fault tolerance Fault tolerant computer systems Graph theory Hamiltonians Interconnection networks (circuit switching)

Community:

  • [ 1 ] [Zhao, Kun]College of Computer and Data Science, Fuzhou University, Fuzhou, China
  • [ 2 ] [Zhuang, Hongbin]College of Computer and Data Science, Fuzhou University, Fuzhou, China
  • [ 3 ] [Li, Xiao-Yan]College of Computer and Data Science, Fuzhou University, Fuzhou, China
  • [ 4 ] [Song, Fangying]School of Mathematics and Statistics, Fuzhou University, Fuzhou, China
  • [ 5 ] [Su, Lichao]College of Computer and Data Science, Fuzhou University, Fuzhou, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 1865-0929

Year: 2022

Volume: 1723 CCIS

Page: 192-204

Language: English

Cited Count:

WoS CC Cited Count: 0

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:98/10066823
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