Complete path embeddings in crossed cubes

Crossed cubes are popular variants of hypercubes. In this paper, we study path embeddings between any two distinct nodes in crossed cubes. We prove two important results in the n-dimensional crossed cube: (a) for any two nodes, all paths whose lengths are greater than or equal to the distance between the two nodes plus 2 can be embedded between the two nodes with dilation 1; (b) for any two integers n ? 2 and l with , there always exist two nodes x and y whose distance is l, such that no path of length l + 1 can be embedded between x and y with dilation 1. The obtained results are optimal in the sense that the dilations of path embeddings are all 1. The results are also complete, because the embeddings of paths of all possible lengths between any two nodes are considered.     

Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u,v∈V(G) are joined by a path of length l for all d_G(u,v)?l?|V(G)|-1, where d_G(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190-1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332-3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ_n, is almost panconnected except the path of length d_CQn(u,v)+1 for any two distinct vertices u,v∈V(CQ_n). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d_CQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,v in CQ_n. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.     

Optimal fault-tolerant embedding of paths in twisted cubes

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let _TQn(V,E)${\mathit{TQ}}_n(V,E)$ denote the n-dimensional twisted cube. We prove that a path of length l   can be embedded between any two distinct nodes with dilation 1 for any faulty set F⊂V(_TQn)∪E(_TQn)$F\subset V({\mathit{TQ}}_n)\cup E({\mathit{TQ}}_n)$ with |F|?n-3$\left|F\right|?n-3$ and any integer l   with 2^n-1-1?l?|V(_TQn-F)|-1$2^{n-1}-1?l?|V({\mathit{TQ}}_n-F)|-1$ (n?3$n?3$). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l   and faulty set size |F|$\left|F\right|$ for a successful embedding are tight. That is, the result does not hold if l?2^n-1-2$l?2^{n-1}-2$ or |F|?n-2$\left|F\right|?n-2$. We also extend the result on (n-3)$(n-3)$-Hamiltonian connectivity of _TQn${\mathit{TQ}}_n$ in the literature.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

Fault-tolerant cycle-embedding of crossed cubes

The crossed cube CQ_n introduced by Efe has many properties similar to those of the popular hypercube. However, the diameter of CQ_n is about one half of that of the hypercube. Failures of links and nodes in an interconnection network are inevitable. Hence, in this paper, we consider the hybrid fault-tolerant capability of the crossed cube. Letting f_e and f_v be the numbers of faulty edges and vertices in CQ_n, we show that a cycle of length l, for any 4?l?|V(CQ_n)|−f_v, can be embedded into a wounded crossed cube as long as the total number of faults (f_v+f_e) is no more than n−2, and we say that CQ_n is (n−2)-fault-tolerant pancyclic. This result is optimal in the sense that if there are n−1 faults, there is no guarantee of having a cycle of a certain length in it.     

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.     

Conditional fault diameter of crossed cubes

The conditional connectivity and the conditional fault diameter of a crossed cube are studied in this work. The conditional connectivity is the connectivity of an interconnection network with conditional faults, where each node has at least one fault-free neighbor. Based on this requirement, the conditional connectivity of a crossed cube is shown to be 2n−2$2n-2$. Extending this result, the conditional fault diameter of a crossed cube is also shown to be D(C_Qn)+3$D\left(C{Q}_n\right)+3$ as a set of 2n−3$2n-3$ node failures. This indicates that the conditional fault diameter of a crossed cube is increased by three compared to the fault-free diameter of a crossed cube. The conditional fault diameter of a crossed cube is approximately half that of the hypercube. In this respect, the crossed cube is superior to the hypercube.     

The panpositionable panconnectedness of crossed cubes

In many parallel and distributed multiprocessor systems, the processors are connected based on different types of interconnection networks. The topological structure of an interconnection network is typically modeled as a graph. Among the many kinds of network topologies, the crossed cube is one of the most popular. In this paper, we investigate the panpositionable panconnectedness problem with respect to the crossed cube. A graph G is r-panpositionably panconnected if for any three distinct vertices x, y, z of G and for any integer \(l_1\) satisfying \(r \le l_1 \le |V(G)| - r - 1\), there exists a path \(P = [x, P_1, y, P_2, z]\) in G such that (i) \(P_1\) joins x and y with \(l(P_1) = l_1\) and (ii) \(P_2\) joins y and z with \(l(P_2) = l_2\) for any integer \(l_2\) satisfying \(r \le l_2 \le |V(G)| - l_1 - 1\), where |V(G)| is the total number of vertices in G and \(l(P_1)\) (respectively, \(l(P_2)\)) is the length of path \(P_1\) (respectively, \(P_2\)). By mathematical induction, we demonstrate that the n-dimensional crossed cube \(CQ_n\) is n-panpositionably panconnected. This result indicates that the path embedding of joining x and z with a mediate vertex y in \(CQ_n\) is extremely flexible. Moreover, applying our result, crossed cube problems such as panpositionable pancyclicity, panpositionably Hamiltonian connectedness, and panpositionable Hamiltonicity can be solved.     

Node-pancyclicity and edge-pancyclicity of crossed cubes

Crossed cubes are important variants of the hypercubes. It has been proven that crossed cubes have attractive properties in Hamiltonian connectivity and pancyclicity. In this paper, we study two stronger features of crossed cubes. We prove that the n-dimensional crossed cube is not only node-pancyclic but also edge-pancyclic for n?2. We also show that the similar property holds for hypercubes.     

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.     

Diagnosability of crossed cubes under the comparison diagnosismodel

Diagnosability of a multiprocessor system is one important study topic in the parallel processing area. As a hypercube variant, the crossed cube has many attractive properties. The diameter, wide diameter and fault diameter of it are all approximately half of those of the hypercube. The power that the crossed cube simulates trees and cycles is stronger than the hypercube. Because of these advantages of the crossed cube, it has attracted much attention from researchers. We show that the n-dimensional crossed cube is n-diagnosable under a major diagnosis model-the comparison diagnosis model proposed by Malek (1980) and Maeng and Malek (1981) if n⩾4. According to this, the polynomial algorithm presented by Sengupta and Dahbura (1992) may be used to diagnose the n-dimensional crossed cube, provided that the number of the faulty nodes in the n-dimensional crossed cube does not exceed n. The conclusion of this paper also indicates that the diagnosability of the n-dimensional crossed cube is the same as that of the n-dimensional hypercube when n>5 and better than that of the n-dimensional hypercube when n=4     

Edge congestion and topological properties of crossed cubes

An n-dimensional crossed cube, CQ_n, is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with Efe's algorithm, which generates one shortest path in O(n²) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortest path routing algorithm, we consider a new performance measure of interconnection networks called edge congestion. Using our shortest path routing algorithm and assuming that message exchange between all pairs of vertices is equally probable, we show that the edge congestion of crossed cubes is the same as that of hypercubes. Using the result of edge congestion, we can show that the bisection width of crossed cubes is 2^n-1. We also prove that wide diameter and fault diameter are [n/2]+2. Furthermore, we study embedding of cycles in cross cubes and construct more types than previous work of cycles of length at least four     

Diagnosability of crossed cubes under the comparison diagnosismodel

Diagnosability of a multiprocessor system is an important study topic in the parallel processing area. As a hypercube variant, the crossed cube has many attractive properties. The diameter, wide diameter and fault diameter of it are all approximately half those of the hypercube. The power with which the crossed cube simulates trees and cycles is stronger than the hypercube. Because of these advantages, the crossed cube has attracted much attention from researchers. In this paper, we show that the n-dimensional crossed cube is n-diagnosable under a major diagnosis model-the comparison diagnosis model proposed by Malek and Maeng (1981) if n ⩾ 4. According to this, the polynomial algorithm presented by Sengupta and Dahbura (1992) may be used to diagnose the n-dimensional crossed cube, provided that the number of the faulty nodes in the n-dimensional crossed cube does not exceed n. The conclusion also indicates that the diagnosability of the n-dimensional crossed cube is the same as that of the n-dimensional hypercube when n ⩾ 5 and better than that of the n-dimensional hypercube when n = 4     

Fault-tolerant embedding of meshes/tori in twisted cubes

Twisted cubes are an important class of hypercube-variant interconnection networks for parallel computing. In this paper, we evaluate the fault-tolerant mesh/torus embedding abilities of twisted cubes. By reducing the fault-tolerant mesh/torus embedding problem to the fault-tolerant pancyclicity, we propose several schemes for embedding meshes/tori in faulty twisted cubes. The obtained results reveal another appealing fault-tolerant feature of twisted cubes.     

Fault-free Hamiltonian cycles in crossed cubes with conditional link faults

The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to 2n − 5 link faults. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its occurrence probability, which is very close to 1.     

The conditional diagnosability of crossed cubes under the comparison model

The growing size of the multiprocessor systems increases their vulnerability to component failures. It is crucial to locate and replace the faulty processors to maintain the system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. The conditional diagnosis requires that for each processor v in a system, all the processors that are directly connected to v do not fail simultaneously. In this paper, we show that the conditional diagnosability of the crossed cubes CQ _n under the comparison diagnosis model is 3n?5 when n≥7. Hence, the conditional diagnosability of CQ _n is three times larger than its classical diagnosability.     

Single-source three-disjoint path covers in cubes of connected graphs

A k-disjoint path cover (k-DPC for short) of a graph is a set of k internally vertex-disjoint paths from given sources to sinks that collectively cover every vertex in the graph. In this paper, we establish a necessary and sufficient condition for the cube of a connected graph to have a 3-DPC joining a single source to three sinks. We also show that the cube of a connected graph always has a 3-DPC joining arbitrary two vertices.     

Optimal virtual network embedding: Energy aware formulation

Network Virtualization is a key component of the Future Internet, providing the dynamic support of different networks with different paradigms and mechanisms in the same physical infrastructure. A major challenge in the dynamic provision of virtual networks is the embedding approach taking energy efficiency into account, while not affecting the overall Virtual Network (VN) acceptance ratio. Previous research focused on either designing heuristic-based algorithms to address the efficient embedding problem or to address the energy impact.This paper proposes an integer linear programming formulation, Energy Aware–Virtual Network Embedding–Node-Link Formulation (EA–VNE–NLF), that solves the online virtual network embedding as an optimization problem, striving for the minimum energy consumption and optimal resource allocation per VN mapping. Two different objective functions are proposed: (i) addressing primarily the resource consumption problem – Bandwidth Consumption Minimization (BCM); (ii) addressing primarily the energy consumption problem – Energy Consumption Minimization (ECM).The performance of each objective function is evaluated by means of simulation and compared with an existing objective function, Weighted Shortest Distance Path (WSDP), that is considered state of the art of the resource allocation problem. The simulation results show that the objective function BCM reduces the energy consumption of the physical network by 14.4%, and improves the embedding factor by 4.3%, consuming almost the same amount of resources as requested, and slightly worsening the VN acceptance ratio by 2.3%. ECM reduces the energy consumption of the physical network by 31.4% and improves the embedding factor by 4.1%, without affecting the VN acceptance ratio when compared to WSDP.