Narrow Results

The Folded Hypercube (FHC) has been proven to be an attractive hypercube-based network. This paper closely compares the FHC to its standard hypercube counterpart from the subcube allocation viewpoint. It is shown that the FHC(n) outperforms the n-dimensional hypercube (n-cube for short) in offering subcubes of size k by a factor of . In an environment where subcubes of the original network must be allocated to incoming tasks, the FHC achieves an excellent processor utilization by assigning subcubes in an efficient and compact manner. Using the concept of virtual hypercubes, an efficient way is suggested to recognize the available subcubes in the FHC by adapting the already developed subcube recognition algorithms. An alternative approach to the subcube recognition problem is also given.

Graph embedding has been known as a powerful tool for implementation of parallel algorithms and simulation of interconnection networks. In this paper, we introduce a technique to obtain a lower bound for the dilation of an embedding. Moreover, we give algorithms for embedding variants of hypercubes with dilation 2 proving that the lower bound obtained is sharp. Further, we compute the exact wirelength of embedding folded hypercubes and augmented cubes into hypercubes.

A network is said to be conditionally faulty if its every vertex is incident to at least g fault-free neighbors, where $g\ge 1$. An n-dimensional folded hypercube $F{Q}_n$ is a well-known variation of an n-dimensional hypercube $Q_n$, which can be constructed from $Q_n$ by adding an edge to every pair of vertices with complementary addresses. In this paper, we define that a network is said to be g-conditionally faulty if its every vertex is incident to at least g fault-free neighbors, and let $F{F}_v$ (respectively, $F{F}_e$) denote the set of faulty vertices (respectively, faulty edges) in $F{Q}_n$. Then, we consider for the cycles embedding properties in $F{Q}_n-F{F}_v-F{F}_e$ with 4-conditionally faulty, as follows:

(1) For $n\ge 3$, $F{Q}_n-F{F}_v-F{F}_e$ contains a fault-free cycle of every even length from 4 to $2^n-2\left|F{F}_v\right|$, where $\left|F{F}_n\right|+\left|F{F}_e\right|\le 2n-5$;

(2) For even $n\ge 4$, $F{Q}_n-F{F}_v-F{F}_e$ contains a fault-free cycle of every odd length from $n+1$ to $2^n-2\left|F{F}_v\right|-1$, where $\left|F{F}_v\right|+\left|F{F}_e\right|\le 2n-5$.

The folded hypercube is a well-known variation of hypercube structure and can be constructed from a hypercube by adding an edge to every pair of vertices with complementary addresses. Let ${FF}_v$ (respectively, ${FF}_e$) denote the set of faulty vertices (respectively, faulty edges) in an $n$-dimensional folded hypercube $F{Q}_n$. In the case that all edges in $F{Q}_n$ are fault-free, Cheng et al. [Cycles embedding on folded hypercubes with faulty vertices, Discrete Appl. Math.161 (2013) 2894–2900] has shown that (1) every fault-free edge of ${FQ}_n-{FF}_v$ lies on a fault-free cycle of every even length from $4$ to $2^n-2\left|{FF}_v\right|$ if $\left|{FF}_v\right|\le n-2$, where $n\ge 3$; and (2) every fault-free edge of ${FQ}_n-{FF}_v$ lies on a fault-free cycle of every odd length from $n+1$ to $2^n-2\left|{FF}_v\right|-1$ if $\left|{FF}_v\right|\le n-2$, where $n\ge 2$ is even. In this paper, we extend Cheng’s result to obtain two further properties, which consider both vertex and edge faults, as follows:

(1) Every fault-free edge of $F{Q}_n-{FF}_v-{FF}_e$ lies on a fault-free cycle of every even length from $4$ to $2^n-2\left|{FF}_v\right|$ if $\left|{FF}_v\right|+\left|{FF}_e\right|\le n-2$, where $n\ge 3$;

(2) Every fault-free edge of $F{Q}_n-{FF}_v-{FF}_e$ lies on a fault-free cycle of every odd length from $n+1$ to $2^n-2\left|{FF}_v\right|-1$ if $\left|{FF}_v\right|+\left|{FF}_e\right|\le n-2$, where $n\ge 2$ is even.