IEICE TRANSACTIONS on Fundamentals
Longest Fault-Free Cycles in Folded Hypercubes with Conditional Faulty Elements
Summary :
An n-dimensional folded hypercube, denoted by FQn, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FFv (respectively, FFe) denote the set of faulty nodes (respectively, faulty links) in FQn. Under the assumption that every fault-free node in FQn is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FFv|+|FFe| ≤ 2n-4 for n ≥ 3, then FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv|. In this paper, we show that, under the same conditional fault model, FQn 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., FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv| if |FFv|+|FFe| ≤ 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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 FQn, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FFv (respectively, FFe) denote the set of faulty nodes (respectively, faulty links) in FQn. Under the assumption that every fault-free node in FQn is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FFv|+|FFe| ≤ 2n-4 for n ≥ 3, then FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv|. In this paper, we show that, under the same conditional fault model, FQn 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., FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv| if |FFv|+|FFe| ≤ 2n-3 for n ≥ 5.
URL: https://global.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 FQn, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FFv (respectively, FFe) denote the set of faulty nodes (respectively, faulty links) in FQn. Under the assumption that every fault-free node in FQn is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FFv|+|FFe| ≤ 2n-4 for n ≥ 3, then FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv|. In this paper, we show that, under the same conditional fault model, FQn 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., FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv| if |FFv|+|FFe| ≤ 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 FQn, is an enhanced n-dimensional hypercube with one extra link between nodes that have the furthest Hamming distance. Let FFv (respectively, FFe) denote the set of faulty nodes (respectively, faulty links) in FQn. Under the assumption that every fault-free node in FQn is incident to at least two fault-free links, Hsieh et al. (Inform. Process. Lett. 110 (2009) pp.41-53) showed that if |FFv|+|FFe| ≤ 2n-4 for n ≥ 3, then FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv|. In this paper, we show that, under the same conditional fault model, FQn 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., FQn-FFv-FFe contains a fault-free cycle of length at least 2n-2|FFv| if |FFv|+|FFe| ≤ 2n-3 for n ≥ 5.
ER -
English
