Longest Fault-Free Cycles in Folded Hypercubes with Conditional Faulty Elements

Wen-Yin HUANG; Jia-Jie LIU; Jou-Ming CHANG; Ro-Yu WU

doi:10.1587/transfun.E97.A.1187

Longest Fault-Free Cycles in Folded Hypercubes with Conditional Faulty Elements

Wen-Yin HUANG, Jia-Jie LIU, Jou-Ming CHANG, Ro-Yu WU

Full Text Views

0

Share
Cite this

Summary :

An n-dimensional folded hypercube, denoted by FQ_n, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FF_v (respectively, FF_e) denote the set of faulty nodes (respectively, faulty links) in FQ_n. Under the assumption that every fault-free node in FQ_n is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FF_v|+|FF_e| ≤ 2n-4 for n ≥ 3, then FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v|. In this paper, we show that, under the same conditional fault model, FQ_n with n ≥ 5 can tolerate more faulty elements and provides the same lower bound of the length of a longest fault-free cycle, i.e., FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v| if |FF_v|+|FF_e| ≤ 2n-3 for n ≥ 5.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1187-1191

Publication Date: 2014/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E97.A.1187

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Wen-Yin HUANG
  National Taipei College of Business
Jia-Jie LIU
  Shih Hsin University
Jou-Ming CHANG
  National Taipei College of Business
Ro-Yu WU
  Lunghwa University of Science and Technology

Keyword

interconnection networks, hypercubes, folded hypercubes, fault-free cycles, conditional fault model

Cite this

Copy

Wen-Yin HUANG, Jia-Jie LIU, Jou-Ming CHANG, Ro-Yu WU, "Longest Fault-Free Cycles in Folded Hypercubes with Conditional Faulty Elements" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 6, pp. 1187-1191, June 2014, doi: 10.1587/transfun.E97.A.1187.
Abstract: An n-dimensional folded hypercube, denoted by FQ_n, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FF_v (respectively, FF_e) denote the set of faulty nodes (respectively, faulty links) in FQ_n. Under the assumption that every fault-free node in FQ_n is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FF_v|+|FF_e| ≤ 2n-4 for n ≥ 3, then FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v|. In this paper, we show that, under the same conditional fault model, FQ_n with n ≥ 5 can tolerate more faulty elements and provides the same lower bound of the length of a longest fault-free cycle, i.e., FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v| if |FF_v|+|FF_e| ≤ 2n-3 for n ≥ 5.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1187/_p

Copy

@ARTICLE{e97-a_6_1187,
author={Wen-Yin HUANG, Jia-Jie LIU, Jou-Ming CHANG, Ro-Yu WU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Longest Fault-Free Cycles in Folded Hypercubes with Conditional Faulty Elements},
year={2014},
volume={E97-A},
number={6},
pages={1187-1191},
abstract={An n-dimensional folded hypercube, denoted by FQ_n, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FF_v (respectively, FF_e) denote the set of faulty nodes (respectively, faulty links) in FQ_n. Under the assumption that every fault-free node in FQ_n is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FF_v|+|FF_e| ≤ 2n-4 for n ≥ 3, then FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v|. In this paper, we show that, under the same conditional fault model, FQ_n with n ≥ 5 can tolerate more faulty elements and provides the same lower bound of the length of a longest fault-free cycle, i.e., FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v| if |FF_v|+|FF_e| ≤ 2n-3 for n ≥ 5.},
keywords={},
doi={10.1587/transfun.E97.A.1187},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Longest Fault-Free Cycles in Folded Hypercubes with Conditional Faulty Elements
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1187
EP - 1191
AU - Wen-Yin HUANG
AU - Jia-Jie LIU
AU - Jou-Ming CHANG
AU - Ro-Yu WU
PY - 2014
DO - 10.1587/transfun.E97.A.1187
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - An n-dimensional folded hypercube, denoted by FQ_n, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FF_v (respectively, FF_e) denote the set of faulty nodes (respectively, faulty links) in FQ_n. Under the assumption that every fault-free node in FQ_n is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FF_v|+|FF_e| ≤ 2n-4 for n ≥ 3, then FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v|. In this paper, we show that, under the same conditional fault model, FQ_n with n ≥ 5 can tolerate more faulty elements and provides the same lower bound of the length of a longest fault-free cycle, i.e., FQ_n-FF_v-FF_e contains a fault-free cycle of length at least 2ⁿ-2|FF_v| if |FF_v|+|FF_e| ≤ 2n-3 for n ≥ 5.
ER -