Pancyclicity of Mobius cubes with faulty nodes

Yang, X.F., Megson, G.M. and Evans, D.J. (2006) Pancyclicity of Mobius cubes with faulty nodes. Microprocessors and Microsystems, 30 (3). pp. 165-172. ISSN 0141-9331 doi: 10.1016/j.micpro.2005.11.001

Abstract/Summary

An interconnection network with n nodes is four-pancyclic if it contains a cycle of length l for each integer l with 4 <= l <= n. An interconnection network is fault-tolerant four-pancyclic if the surviving network is four-pancyclic in the presence of faults. The fault-tolerant four-pancyclicity of interconnection networks is a desired property because many classical parallel algorithms can be mapped onto such networks in a communication-efficient fashion, even in the presence of failing nodes or edges. Due to some attractive properties as compared with its hypercube counterpart of the same size, the Mobius cube has been proposed as a promising candidate for interconnection topology. Hsieh and Chen [S.Y. Hsieh, C.H. Chen, Pancyclicity on Mobius cubes with maximal edge faults, Parallel Computing, 30(3) (2004) 407-421.] showed that an n-dimensional Mobius cube is four-pancyclic in the presence of up to n-2 faulty edges. In this paper, we show that an n-dimensional Mobius cube is four-pancyclic in the presence of up to n-2 faulty nodes. The obtained result is optimal in that, if n-1 nodes are removed, the surviving network may not be four-pancyclic. (C) 2005 Elsevier B.V. All rights reserved.

Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/15480
Item Type	Article
Refereed	Yes
Divisions	Science
Uncontrolled Keywords	interconnection network, Mobius cube, fault tolerance, pancyclicity, fault-tolerant pancyclicity
Download/View statistics	View download statistics for this item