Fault-tolerant path embedding in folded hypercubes with both node and edge faults

Che Nan Kuo, Hsin Hung Chou, Nai Wen Chang, Sun Yuan Hsieh

研究成果: Article同行評審

36 引文 斯高帕斯(Scopus)

摘要

The folded hypercube FQn is a well-known variation of the hypercube structure. FQn is superior to Qn in many measurements, such as diameter, fault diameter, connectivity, and so on. Let V(FQn) (resp. E(FQn)) denote the set of faulty nodes (resp. faulty edges) in FQn. In the case that all nodes in FQ n are fault-free, it has been shown that FQn contains a fault-free path of length 2n-1 (resp. 2n-2) between any two nodes of odd (resp. even) distance if E(FQn)≤n-1, where n≥1 is odd; and FQn contains a fault-free path of length 2n-1 between any two nodes if E(FQn)≤n-2, where n≥2 is even. In this paper, we extend the above result to obtain two further properties, which consider both node and edge faults, as follows: FQn contains a fault-free path of length at least 2n-2V(FQn)-1 (resp. 2n-2V(FQn)-2) between any two fault-free nodes of odd (resp. even) distance if V(FQn)+E(FQn)≤n-1, where n≥1 is odd.FQn contains a fault-free path of length at least 2n-2V(FQn)-1 between any two fault-free nodes if V(FQ n)+E(FQn)≤n-2, where n≥2 is even.

原文English
頁(從 - 到)82-91
頁數10
期刊Theoretical Computer Science
475
DOIs
出版狀態Published - 2013 3月 4

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 一般電腦科學

指紋

深入研究「Fault-tolerant path embedding in folded hypercubes with both node and edge faults」主題。共同形成了獨特的指紋。

引用此