Embedding of cycles in the faulty hypercube

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

1 Citation (Scopus)

Abstract

Let fv (respectively, fe) denote the number of faulty vertices (respectively, edges) in an n-dimensional hypercube. In this paper, we show that a fault-free cycle of length of at least 2n -2f v can be embedded in an n-dimensional hypercube with fe ≤ n - 2 and fv + fe ≤ 2n - 4. Our result not only improves the previously best known result of Sengupta (1998) where fv > 0 or fe ≤ n - 2 and fv + fe ≤ n-1 were assumed, but also extends the result of Fu (2003) where only the faulty vertices are considered.

Original languageEnglish
Title of host publicationAdvances in Computer Systems Architecture - 10th Asia-Pacific Conference, ACSAC 2005, Proceedings
Pages229-235
Number of pages7
DOIs
Publication statusPublished - 2005 Dec 1
Event10th Asia-Pacific Conference on Advances in Computer Systems Architecture, ACSAC 2005 - Singapore, Singapore
Duration: 2005 Oct 242005 Oct 26

Publication series

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

Other

Other10th Asia-Pacific Conference on Advances in Computer Systems Architecture, ACSAC 2005
Country/TerritorySingapore
CitySingapore
Period05-10-2405-10-26

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Embedding of cycles in the faulty hypercube'. Together they form a unique fingerprint.

Cite this