The balanced hypercube is a variant of the hyper-cube structure and has desirable properties like connectivity, regularity, and symmetry. The cycle is a popular interconnection topology and has been widely used in distributed-memory parallel computers. Moreover, parallel algorithms of cycles have been extensively developed and used. The problem of how to embed cycles into a host graph has attracted a great attention in recent years. However, there is no systematic method proposed to generate the desired cycles in balanced hypercubes. In this paper, we develop systematic linear time algorithm to construct cycles for the balanced hypercube.

The twisted cube TQnis an alternative to the popular hypercube network and some interesting properties of TQnwere investigated recently. The problem of how to embed cycles into a host graph has attracted a great attention in recent years. However, there are few systematic methods proposed to generate the desired cycles in TQn. In this paper, we provide two kinds of systematic methods of embedding cycles into TQn.

System level diagnosis is an important technique for fault detection and location in multiprocessor computing systems. Adaptive diagnosis, proposed by Nakajima, is a practical system level diagnostic scheme; the main design objective of an adaptive diagnostic scheme is to reduce the number of test rounds, as well as the total number of tests. The hierarchical crossed cube draws upon constructions used within both the hypercube and the crossed cube, giving it many desirable features such as symmetry and logarithmic diameter, making it suitable for massively parallel systems with thousands of processors. In this paper, we first show that the diagnosability of a hierarchical crossed cube, HCCk,n, is k+n, and then propose a scheme that completely diagnoses a HCCk,n within three test rounds, and at most N+⌈(k+n+2)/2⌉ × ⌊(k+n+2)/2⌋ tests, where N=2k+2nis the number of vertices of HCCk,n. Our diagnostic scheme has the optimal number of test rounds. Moreover, most of our proofs are applicable not just to hierarchical crossed cubes but also to hierarchical interconnection networks formed by replacing crossed cubes with other appropriate interconnection networks.

There is a growing demand for fault diagnosis to increase the reliability of systems. Diagnosis by comparison is a realistic approach to the fault diagnosis of multiprocessor systems. In this paper, we considern-dimensional hypercube-like networks forn≥ 5. We propose an efficient fault diagnosis algorithm forn-dimensional hypercube-like networks under the MM comparison model by exploiting the Hamiltonian and extended-star properties. Applying our algorithm, the faulty processors inn-dimensional hypercubes,n-dimensional crossed cubes,n-dimensional twisted cubes, andn-dimensional Möbius cubes can all be diagnosed in linear time provided the number of faulty processors is not more than the dimensionn.

The problem of whether or not there are mutually independent hamiltonian cycles in interconnection networks has attracted a great attention in recent years. In this paper, we will show that most of n-dimensional hypercube-like graphs have two mutually independent hamiltonian cycles. Moreover, we also develop a systematic linear time algorithm for constructing two mutually independent hamiltonian cycles in the n-dimensional hypercube Qn, n > 3.

The hypercube has been widely used as the interconnection network in parallel computers. The crossed cube is a variation of hypercube and preserves many of its desirable properties. The hierarchical crossed cube draws upon constructions used within the hypercube and also the crossed cube. The hierarchical crossed cube is suitable for massively parallel systems with thousands of processors and owns many alluring features, such as symmetry and logarithmic diameter. In this paper, we adopt the concept of Hamiltonian cycles pattern to provide a constructive algorithm to generate a Hamiltonian cycle of the hierarchical crossed cube.

Diagnosability has played an important role in the reliability of an interconnection network. The classical problem of fault diagnosis is discussed widely and the diagnosability of many well-known networks have been explored. We introduce a new measure of diagnosability, called conditional diagnosability, by restricting that any faulty set cannot contain all the neighbors of any vertex in the graph. Based on this requirement, the conditional diagnosability of the n-dimensional hypercube is shown to be 4(n - 2) +1, which is about four times as large as the classical diagnosability. Besides, we propose some useful conditions for verifying if a system is t-diagnosable and introduce a new concept, called a strongly t-diagnosable system, under the PMC model. Applying these concepts and conditions, we investigate some t-diagnosable networks which are also strongly t-diagnosable.

Diagnosability is an important factor in measuring the reliability of an interconnection network, while the (node) connectivity is used to measure the fault tolerance of an interconnection network. We observe that there is a close relationship between the connectivity and the diagnosability. According to our results, a t-regular and t-connected network with at least 2t + 3 nodes is t-diagnosable. Furthermore, the diagnosability of the product networks is also investigated in this work. The product networks, including hypercube, mesh, and tori, comprise very important classes of interconnection networks. Herein, different combinations of t-diagnosable and t-connected are employed to study the diagnosability of the product networks.

The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks has been explored. We consider the diagnosability of a family of networks, called the matching composition network (MCN); a perfect matching connects two components. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the hypercube Qn, the crossed cube CQ/sub n/, the twisted cube TQ/sub n/, and the Mobius cube MQ/sub n/ can all proven to be n, for n/spl ges/4. In particular, we show that the diagnosability of the four-dimensional hypercube Q/sub 4/ is 4, which is not previously known.