Narrow Results

This paper describes a new fault-tolerant routing algorithm for k-ary n-cubes using the concept of "probability vectors". To compute these vectors, a node determines first its faulty set, which represents the set of all its neighbouring nodes that are faulty or unreachable due to faulty links. Each node then calculates a probability vector, where the lth element represents the probability that a destination node at distance l cannot be reached through a minimal path due to a faulty node or link. The probability vectors are used by all the nodes to achieve an efficient fault-tolerant routing in the network. An extensive performance analysis conducted in this study reveals that the proposed algorithm exhibits good fault-tolerance properties in terms of the achieved percentage of reachability and routing distances.

In this paper a parallel algorithm for solving systems of linear equation on the k-ary n-cube is presented and evaluated for the first time. The proposed algorithm is of O(N³/kⁿ) computation complexity and uses O(Nn) communication time to factorize a matrix of order N on the k-ary n-cube. This is better than the best known results for the hypercube, O(N log kⁿ), and the mesh, , each with approximately kⁿ nodes. The proposed parallel algorithm takes advantage of the extra connectivity in the k-ary n-cube in order to reduce the communication time involved in tasks such as pivoting, row/column interchanges, and pivot row and multipliers column broadcasts.

The $k$-ary $n$-cube network is known as one of the most attractive interconnection networks for parallel and distributed systems. A many-to-many $m$-disjoint path cover ($m$-DPC for short) of a graph is a set of $m$ vertex-disjoint paths joining two disjoint vertex sets $S$ and $T$ of equal size $m$ that altogether cover every vertex of the graph. The many-to-many $m$-DPC is classified as paired if each source in $S$ is further required to be paired with a specific sink in $T$, or unpaired otherwise. In this paper, we consider the unpaired many-to-many $m$-DPC problem of faulty bipartite $k$-ary $n$-cube networks $Q_n^k$, where the sets $S$ and $T$ are chosen in different parts of the bipartition. We show that, every bipartite $Q_n^k$, under the condition that $f$ or less faulty edges are removed, has an unpaired many-to-many $m$-DPC for any $f$ and $m\ge 1$ subject to $f+m\le 2n-1$. The bound $2n-1$ is tight here.

Let $G$ be an undirected graph. An $H$-structure-cut (resp. $H$-substructure-cut) of $G$ is a set of subgraphs of $G$, if any, whose deletion disconnects $G$, where the subgraphs deleted are isomorphic to a certain graph $H$ (resp. where for any $T^{\prime }$ of the subgraphs deleted, there is a subgraph $T$ of $G$, isomorphic to $H$, such that $T^{\prime }$ is a subgraph of $T$). $G$ is super$H{|}_M$-connected (resp. super sub-$H{|}_M$-connected) if the deletion of an arbitrary minimum $H$-structure-cut (resp. minimum $H$-substructure-cut) isolates a component isomorphic to a certain graph $M$. The $k$-ary $n$-cube $Q_n^k$ is one of the most attractive interconnection networks for multiprocessor systems. In this paper, we prove that $Q_n^k$ with $n\ge 3$ is super sub-$C_k{|}_{K_1}$-connected if $k\ge 3$ and $k$ is odd, and super $C_k{|}_{C_k}$-connected if $k\ge 5$ and $k$ is odd.

This paper derives the conditional node connectivity of the k-ary n-cube interconnection network under the condition of forbidden faulty sets (i.e. assuming that each non-faulty processor has at least one non-faulty neighbor). It is shown that under this condition and for k≥4 and n≥2, the k-ary n-cube, whose connectivity is 2n, can tolerate up to 4n-3 faulty nodes without becoming disconnected. The conditional node connectivity in this case is therefore 4n-2. For k=3 and n≥2 the established conditional node connectivity is 4n-3. The result for the remaining smaller values of k and n are also obtained.