Fault-free cycles in conditional faulty folded hypercubes

Che Nan Kuo, Sun Yuan Hsieh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

An n-dimensional folded hypercube FQ n is an attractive variance of an n-dimensional hypercube Q n , which is obtained by a standard hypercube with some extra edges established between its vertices. FQ n for any odd n is known to be bipartite. In this paper, for any FQ n (n > 2) with at most 2n-3 faulty edges in which each vertex is incident with at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2 n , and when n > 2 is even, there also exists a fault-free cycle of every odd length from n + 1 to 2 n - 1. The result is optimal with respect to the number of edges faults tolerated.

Original languageEnglish
Title of host publicationAlgorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings
Pages439-448
Number of pages10
DOIs
Publication statusPublished - 2009 Sep 21
Event9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009 - Taipei, Taiwan
Duration: 2009 Jun 82009 Jun 11

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5574 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009
CountryTaiwan
CityTaipei
Period09-06-0809-06-11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fault-free cycles in conditional faulty folded hypercubes'. Together they form a unique fingerprint.

  • Cite this

    Kuo, C. N., & Hsieh, S. Y. (2009). Fault-free cycles in conditional faulty folded hypercubes. In Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings (pp. 439-448). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5574 LNCS). https://doi.org/10.1007/978-3-642-03095-6_42