Fault-tolerant hamiltonicity of augmented cubes under the conditional fault model

Sun-Yuan Hsieh, Yi Ru Cian

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

Abstract

The augmented cube is a variation of hypercubes, which possesses many properties superior to the hypercubes. In this paper, we show that, for any n-dimensional augmented cube (n > 3) with 4n - 8 faulty edges in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated.

Original languageEnglish
Title of host publicationAlgorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings
Pages673-683
Number of pages11
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-tolerant hamiltonicity of augmented cubes under the conditional fault model'. Together they form a unique fingerprint.

  • Cite this

    Hsieh, S-Y., & Cian, Y. R. (2009). Fault-tolerant hamiltonicity of augmented cubes under the conditional fault model. In Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings (pp. 673-683). (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_63