Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11]

@

Journal of Information Science and Engineering, Vol. 29 No. 4, pp. 777-783 (July 2013)


Largest Connected Component of a k-ary n-cube with Faulty Vertices*


QIANG DONG+
Web Sciences Center
School of Computer Science and Engineering
University of Electronic Science and Technology of China
Chengdu, 611731 P.R. China

The k-ary n-cube is one of the most popular interconnection networks for parallel computing. This paper addresses the size of a largest connected component of a faulty k-ary n-cube. We prove that, in a k-ary n-cube (k >= 4 and n >= 2) with up to 4nV2 faulty vertices, all fault-free vertices but at most two constitute a connected component. Moreover, this assertion holds if and only if the set of all faulty vertices is equal to the neighborhood of a pair of fault-free adjacent vertices.

Keywords: interconnection networks, k-ary n-cube, largest connected component, fault tolerance, parallel computing

Full Text () Retrieve PDF document (201307_11.pdf)

Received March 31, 2011; accepted July 25, 2011.
Communicated by Chia-Feng Juang.
* This work was supported by National Nature Science Foundation of China (No. 61003231, No. 61103109), Research Fund for the Doctoral Program of Higher Education of China (No. 20120185120017), China Postdoctoral Science Foundation (No. 2013M531951), and Fundamental Research Funds for the Central Universities (No. ZYGX2011J057, No. ZYGX2012J071, No. ZYGX2012J085).
+ Corresponding author: Qiang Dong (dongq@uestc.edu.cn).