Accessibility navigation


On the maximal connected component of hypercube with faulty vertices

Yang, X. F., Evans, D. J., Chen, B., Megson, G. M. and Lai, H. J. (2004) On the maximal connected component of hypercube with faulty vertices. International Journal of Computer Mathematics, 81 (5). pp. 515-525. ISSN 0020-7160

Full text not archived in this repository.

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1080/00207160410001661726

Abstract/Summary

In evaluating an interconnection network, it is indispensable to estimate the size of the maximal connected components of the underlying graph when the network begins to lose processors. Hypercube is one of the most popular interconnection networks. This article addresses the maximal connected components of an n -dimensional cube with faulty processors. We first prove that an n -cube with a set F of at most 2n - 3 failing processors has a component of size greater than or equal to2(n) - \F\ - 1. We then prove that an n -cube with a set F of at most 3n - 6 missing processors has a component of size greater than or equal to2(n) - \F\ - 2.

Item Type:Article
Refereed:Yes
Divisions:Faculty of Science
ID Code:15464
Uncontrolled Keywords:interconnection network, fault tolerance, maximal connected component, hypercube

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation