Embedding meshes into crossed cubes

Crossed cubes are important variants of hypercubes. In this paper, we consider embeddings of meshes in crossed cubes. The major research findings in this paper are: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 2. The obtained results are optimal in the sense that the dilations of the embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion because it has the smallest expansion 1.     

Embedding meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ_n(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in LTQ_n with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in LTQ_n with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4  × (2ⁿ⁻² − 1) mesh can be embedded in LTQ_n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.     

Embedding meshes into twisted-cubes

The n-dimensional twisted-cube, TN_n, is a variation of the hypercube. In this paper, we study embedding of meshes into TN_n. We prove three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded into TN_n with dilation 1 and expansion 1. (2) For any integer n ? 4, an m × k(m ? 3, k ? 3) mesh cannot be embedded into TN_n with dilation 1. (3) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded into TN_n with dilation 2 and expansion 1.     

Embedding a family of disjoint 3D meshes into a crossed cube

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint 3D meshes into a crossed cube. Two major contributions of this paper are: (1) for n?4, a family of two disjoint 3D meshes of size 2×2×2^n-3 can be embedded in an n-D crossed cube with unit dilation and unit expansion, and (2) for n?6, a family of four disjoint 3D meshes of size 4×2×2^n-5 can be embedded in an n-D crossed cube with unit dilation and unit expansion. These results mean that a family of two or four 3D-mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends the results recently obtained by Fan and Jia [J. Fan, X. Jia, Embedding meshes into crossed cubes, Information Sciences 177(15) (2007) 3151-3160].     

Geodesic pancyclicity of twisted cubes

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. An n-dimensional twisted cube, TQ_n, is an important variation of the hypercube Q_n and preserves many of its desirable properties. The problem of embedding linear arrays and cycles into a host graph has attracted substantial attention in recent years. The geodesic cycle embedding problem is for any two distinct vertices, to find all the possible lengths of cycles that include a shortest path joining them. In this paper, we prove that TQ_n is geodesic 2-pancyclic for each odd integer n ? 3. This result implies that TQ_n is edge-pancyclic for each odd integer n ? 3. Moreover, TQ_n × K₂ is also demonstrated to be geodesic 4-pancyclic.     

Embedding a family of disjoint multi-dimensional meshes into a crossed cube

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint multi-dimensional meshes into a crossed cube. We prove that for n?4 and 1?m?⌊n/2⌋−1, a family of m² disjoint k-dimensional meshes of size t₁²×t₂²×?×tk² each can be embedded in an n-dimensional crossed cube with unit dilation, where and max1?i?k{ti}?n−2m−1. This result means that a family of mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends some recently obtained results.     

Embedding multi-dimensional meshes into twisted cubes

The twisted cube is an important variant of the most popular hypercube network for parallel processing. In this paper, we consider the problem of embedding multi-dimensional meshes into twisted cubes in a systematic way. We present a recursive method for embedding a family of disjoint multi-dimensional meshes into a twisted cube with dilation 1 and expansion 1. We also prove that a single multi-dimensional mesh can be embedded into a twisted cube with dilation 2 and expansion 1. Our work extends some previously known results.     

Vertex-pancyclicity of twisted cubes with maximal faulty edges

The n-dimensional twisted cube, denoted by TQ _n , a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, we show that every vertex in TQ _n lies on a fault-free cycle of every length from 6 to 2 ⁿ , even if there are up to n?2 link faults. We also show that our result is optimal.     

On embedding cycles into faulty twisted cubes

The twisted cube TQ_n is an alternative to the popular hypercube network. Recently, some interesting properties of TQ_n were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f_e and f_v be the numbers of faulty edges and faulty vertices in TQ_n, respectively. We show that, with f_e + f_v ? n − 2, a faulty TQ_n still contains a cycle of length l for every 4 ? l ? ∣V(TQ_n)∣ − f_v and odd integer n ? 3.     

One-to-one communication in twisted cubes under restricted connectivity

The dimensions of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all positive integers. Then, we introduce the concept of the restricted faulty set into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQ _n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, which is almost twice as that of TQ _n under the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we provide an O(NlogN) fault-free unicast algorithm and simulations result of the expected length of the fault-free path obtained by our algorithm, where N denotes the node number of TQ _n . Finally, we propose a polynomial algorithm to check whether the faulty node set satisfies the condition that each node of the n-dimensional twisted cube TQ _n has at least one fault-free neighbor.     

Embedding of Cycles in Twisted Cubes with Edge-Pancyclic

In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4≤l≤2 ⁿ , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2 ⁿ , and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n ²+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ _n for any (u,v)∈E(TQ _n ) and any integer l with 4≤l≤2 ⁿ .     

Embedding a long fault-free cycle in a crossed cube with more faulty nodes

The crossed cube is an important variant of the most popular hypercube network for parallel computing. In this paper, we consider the problem of embedding a long fault-free cycle in a crossed cube with more faulty nodes. We prove that for n?5 and f?2n−7, a fault-free cycle of length at least n²−f−(n−5) can be embedded in an n-dimensional crossed cube with f faulty nodes. Our work extends some previously known results in the sense of the maximum number of faulty nodes tolerable in a crossed cube.     

Hamilton-connectivity and cycle-embedding of the Möbius cubes

The recently introduced interconnection network, the Möbius cube, is an important variant of the hypercube. This network has several attractive properties compared with the hypercube. In this paper, we show that the n-dimensional Möbius cube M_n is Hamilton-connected when n?3. Then, by using the Hamilton-connectivity of M_n, we also show that any cycle of length l (4?l?2ⁿ) can be embedded into M_n with dilation 1 (n?2). It is a fact that the n-dimensional hypercube Q_n does not possess these two properties.     

Fault-Tolerant Hamiltonicity of Twisted Cubes

The twisted cube TQ_n, is derived by changing some connection of hypercube Q_n according to specific rules. Recently, many topological properties of this variation cube are studied. In this paper, we consider a faulty twisted n-cube with both edge and/or node faults. Let F be a subset of V(TQ_n)∩E(TQ_n), we prove that TQ_n−F remains hamiltonian if |F|⩽n−2. Moreover, we prove that there exists a hamiltonian path in TQ_n−F joining any two vertices u, v in V(TQ_n)−F if |F|⩽n−3. The result is optimum in the sense that the fault-tolerant hamiltonicity (fault-tolerant hamiltonian connectivity respectively) of TQ_n is at most n−2 (n−3 respectively).     

Fault-tolerant edge-pancyclicity of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a new variant of the hypercube, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of LTQ_n, and shows that if LTQ_n (n ? 3) contains at most n − 3 faulty vertices and/or edges then, for any fault-free edge e and any integer ? with 6 ? ? ? 2ⁿ − f_v, there is a fault-free cycle of length ? containing the edge e, where f_v is the number of faulty vertices. The result is optimal in some senses. The proof is based on the recursive structure of LTQ_n.     

Reconfiguration of Rings and Meshes in Faulty Hypercubes

In this paper we present schemes for reconfiguration of embedded task graphs in hypercubes. Previous results, which use either fault-tolerant embedding or an automorphism approach, can be expensive in terms of either the required number of spare nodes or reconfiguration time. Using the free dimension concept, we combine the above two approaches in our schemes which can tolerate about n faulty nodes under the worst case while keeping task migration time small. With expansion-2 initial embedding, three distributed reconfiguration schemes are presented in this paper. The first scheme, applied to chains and rings, can tolerate any ƒ ≤ n − 2 faulty nodes in an n-dimensional hypercube. The second and third schemes are applied to meshes or tori. For a mesh or torus of size 2^m₁ 1 ··· 1 2^m_d, the second scheme can tolerate any ƒ ≤ m_i − 1 faulty nodes, where m_i is the largest direction of the mesh and n = m₁ + ··· + m_d + 1. By embedding two copies of meshes or tori in cube, the third scheme can tolerate any ƒ ≤ n − 1 faulty nodes with the dilation of embedding after reconfiguration degraded to 2. The third scheme is quite general and can be applied to any task graph.     

A note on cycle embedding in hypercubes with faulty vertices

Let fv denote the number of faulty vertices in an n-dimensional hypercube. This note shows that a fault-free cycle of length of at least n²−2fv can be embedded in an n-dimensional hypercube with fv=2n−3 and n?5. This result not only enhances the previously best known result, and also answers a question in [J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821-832].     

Edge-fault-tolerant vertex-pancyclicity of augmented cubes

The n-dimensional augmented cube, denoted as AQn, a variation of the hypercube, possesses some properties superior to those of the hypercube. In this paper, we show that every vertex in AQn lies on a fault-free cycle of every length from 3 to n², even if there are up to n−1 edge faults. We also show that our result is optimal.     

Embedding Meshes on the Star Graph

We develop algorithms for mapping n-dimensional meshes on a star graph of degree n with expansion 1 and dilation 3. We show that an n-degree star graph can efficiently simulate an n-dimensional mesh.