Narrow Results

Given a shortest path routing algorithm of an interconnection network, the edge congestion is one of the important factors to evaluate the performance of this algorithm. In this paper, we consider the twisted cube, a variation of the hypercube with some better properties, and review the existing shortest path routing algorithm⁸. We find that its edge congestion under the routing algorithm is high. Then, we propose a new shortest path routing algorithm and show that our algorithm has optimum time complexity O(n) and optimum edge congestion 2ⁿ. Moreover, we calculate the bisection width of the twisted cube of dimension n.

We consider routing in hypercube networks with a very large number (i.e., up to a constant fraction) of faulty nodes. Simple and natural conditions are identified under which hypercube networks with a very large number of faulty nodes still remain connected. The conditions can be detected and maintained in a distributed manner based on localized management. Efficient routing algorithms on hypercube networks satisfying these conditions are developed. For a hypercube network that satisfies the conditions and may contain up of 37.5% faulty nodes, our algorithms run in linear time and for any two given non-faulty nodes find a routing path of length bounded by four times the Hamming distance between the two nodes. Moreover, our algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors' status and no global information of the network is required by the algorithms.

Index-shuffle graphs are a family of bounded-degree hypercube-like interconnection networks for parallel computers, introduced by [Baumslag and Obrenić (1997): Index-Shuffle Graphs, …], as an efficient substitute for two standard families of hypercube derivatives: butterflies and shuffle-exchange graphs. In the theoretical framework of graph embedding and network emulations, this paper shows that the index-shuffle graph efficiently approximates the direct-product structure of the hypercube, and thereby has a unique potential to approximate efficiently all of its derivatives.

One of the consequences of our results is that any member of the following group of standard bounded-degree hypercube derivatives: butterflies, shuffles, tori, meshes of trees, is emulated by the index-shuffle graph with a slowdown in the order of the logarithm of the slowdown of the most efficient emulation achieved by any other member of this group.

Emulation algorithms are presented where the emulation host is the n-dimensional index-shuffle graph Ψ_n, having N=2ⁿ nodes. The emulated graph G is a direct product of the form: G=F₀×F₁×⋯×F_k-1 where k is a power of 2, and each factor F_i is an instance of any of the following three graph families: cycle, complete binary tree, X-tree. Let the size of each factor be |F_i|≤2^n_f, where k·n_f≤n. The index-shuffle graph Ψ_n, emulates any factor F_i in the product G with slowdown: O(log k) + O(log n_f), which is O(log n) = O(loglog N). Any collection of 2^ℓ copies of the product G, such that: ℓ+k·n_f≤n is emulated by the index-shuffle graph Ψ_n simultaneously, without any additional slowdown. Relaxing the assumption that k is a power of 2 introduces an additional factor of O(lg*N) into the slowdown.

Extensive experiments and experience have shown that the well-known hypercube networks are highly fault tolerant. What is frustrating is that it seems very difficult to properly formulate and formally prove this important fact, despite extensive research efforts in the past two decades. Most proposed fault tolerance models for hypercube networks are only able to characterize very rare extreme situations thus significantly underestimating the fault tolerance power of hypercube networks, while for more realistic fault tolerance models, the analysis becomes much more complicated. In this paper, we develop new techniques that enable us to analyze a more realistic fault tolerance model and derive lower bounds for the probability of hypercube network fault tolerance in terms of node failure probability. Our results are both theoretically significant and practically important. From the theoretical point of view, our method offers very general and powerful techniques for formally proving lower bounds on the probability of network connectivity, while from the practical point of view, our results provide formally proven and precisely given upper bounds on node failure probabilities for manufacturers to achieve a desired probability for network connectivity. Our techniques are also useful and powerful for analysis of the performance of routing algorithms, and applicable to the study of other hierarchical network structures and to other network communication problems.

Two hamiltonian paths P₁ = 〈v₁, v₂, …, v_n(G) 〉 and P₂ = 〈 u₁, u₂, …, u_n(G) 〉 of G are independent if v₁ = u₁, v_n(G) = u_n(G), and v_i ≠ u_i for 1 < i < n(G). A set of hamiltonian paths {P₁, P₂, …, P_k} of G are mutually independent if any two different hamiltonian paths in the set are independent. A bipartite graph G is hamiltonian laceable if there exists a hamiltonian path joining any two nodes from different partite sets. A bipartite graph is k-mutually independent hamiltonian laceable if there exist k-mutually independent hamiltonian paths between any two nodes from different partite sets. The mutually independent hamiltonian laceability of bipartite graph G, IHP_L(G), is the maximum integer k such that G is k-mutually independent hamiltonian laceable. Let Q_n be the n-dimensional hypercube. We prove that IHP_L(Q_n) = 1 if n ∈ {1,2,3}, and IHP_L(Q_n) = n - 1 if n ≥ 4. A hamiltonian cycle C of G is described as 〈 u₁, u₂, …, u_n(G), u₁ 〉 to emphasize the order of nodes in C. Thus, u₁ is the beginning node and u_i is the i-th node in C. Two hamiltonian cycles of G beginning at u, C₁ = 〈 v₁, v₂, …, v_n(G), v₁ 〉 and C₂ = 〈 u₁, u₂, …, u_n(G), u₁ 〉, are independent if u = v₁ = u₁, and v_i ≠ u_i for 1 < i ≤ n(G). A set of hamiltonian cycles {C₁, C₂, …, C_k} of G are mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonianicity of graph G, IHC(G), is the maximum integer k such that for any node u of G there exist k-mutually independent hamiltonian cycles of G starting at u. We prove that IHC(Q_n) = n - 1 if n ∈ {1,2,3} and IHC(Q_n) = n if n ≥ 4.

Current studies of "messy" broadcasting have so far concentrated on finding worst-case times. However, such worst-case scenarios are extremely unlikely to occur in general. Hence, determining average-case times or tight upper bounds for completing "messy" broadcasting in various network topologies is both necessary and meaningful in practice. In this paper, we focus on seeking the average-case "messy" broadcast times of stars, paths, cycles, and d-ary trees, and finding good upper bounds for hypercubes. Finally, we derive a recursive formula to express the average-case time for a specific "messy" broadcast model on a complete graph using a classical occupancy problem in probability theory, and provide a nice simulation result which indicates that this model behaves like classical broadcasting.

In this paper we study the fault diameter of the n-dimensional hypercube (or n-cube for short), Q_n, for n ≥ 3. Let F be a set of hybrid node-faults and/or link-faults in Q_n such that every node of Q_n is still connected to at least one fault-free node by a fault-free link. Then we compute the exact diameter of Q_n - F for |F| ≤ 2n - 3. As an immediate consequence, our result improves upon those presented by S. Latifi (1993), in which only node-faults were addressed.

Assume that n is a positive integer with n ≥ 4 and F is a subset of the edges of the hypercube Q_n with |F| ≤ n-4. Let u, x be two distinct white vertices of Q_n and v, y be two distinct black vertices of Q_n, where black and white refer to the two parts of the bipartition of Q_n. Let l₁ and l₂ be odd integers, where l₁ ≥ d_Qn-F(u, v), l₂ ≥ d_Qn-F(x,y), and l₁ + l₂ = 2ⁿ - 2. Moreover, let l₃ and l₄ be even integers, where l₃ ≥ d_Qn-F(u,x), l₄ ≥ d_Qn-F(v,y), and l₃+l₄ = 2ⁿ - 2. In this paper, we prove that there are two disjoint paths P₁ and P₂ such that (1) P₁ is a path joining u to v with length l(P₁) = l₁, (2) P₂ is a path joining x to y with l(P₂) = l₂, and (3) P₁ ∪ P₂ spans Q_n - F. Moreover, there are two disjoint paths P₃ and P₄ such that (1) P₃ is a path joining u to x with l(P₃) = l₃, (2) P₄ is a path joining v to y with l(P₄) = l₄, and (3) P₃ ∪ P₄ spans Q_n - F except the following cases: (a) l₃ = 2 with d_Qn-F(u,x) = 2 and d_Qn-F-{v,y}(u,x) > 2, and (b) l₄ = 2 with d_Qn-F(v,y) = 2 and d_Qn-F-{u,x}(v,y) > 2.

In this paper, we consider the conditionally faulty graphs G that each vertex of G is incident with at least m fault-free edges, 2 ≤ m ≤ n - 1. We extend the limitation m ≥ 2 in all previous results of edge-bipancyclicity with faulty edges and faulty vertices. Let f_e (respectively, f_v) denotes the number of faulty edges (respectively, faulty vertices) in an n-dimensional hypercube Q_n. For all m, we show that every fault-free edge of Q_n lies on a fault-free cycle of every even length from 4 to |V| - 2f_v inclusive provided f_e + f_v ≤ n - 2. This result is not only optimal, but also improves on the previously best known results reported in the literature.

The hypercube is one of the most popular interconnection networks due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. In this paper, we introduce a tree called l-sibling trees and the main results obtained in this paper are: (1) For r ≥ 1, the minimum wirelength of embedding r-dimensional hypercube into r-dimensional l-sibling tree. (2) For r ≥ 1, embedding of r-dimensional extended l-sibling tree into caterpillar with minimum dilation. (3) Based on the proof of (1), we provide an O(r)-linear time algorithm to compute the minimum wirelength of embedding r-dimensional hypercube into r-dimensional l-sibling tree.

The hypercubic family of interconnection networks, encompassing the hypercube and its derivatives and variants, has a wide range of applications in parallel processing. Various problems in general complex networks can be addressed by choosing a hypercubic network as a skeleton. In this paper, we provide insight into why hypercubic networks are suitable as network skeletons and discuss a mapping scheme to take advantage of the symmetry of such networks for developing efficient algorithms.

Let $G$ be a connected graph with minimum degree at least $n$ and let $h$ be an integer such that $0\le h<n.$ The conditional $h$-edge ($h$-vertex) cut of $G$ is defined as a set $F$ of edges (vertices) of $G$ whose removal disconnects $G$ leaving behind components of minimum degree at least $h.$ The characterization of a minimum $h$-vertex cut of the $n$-dimensional hypercube $Q_n$ is known. In this paper, we characterize a minimum $h$-edge cut of $Q_n.$ Also, we obtain a sharp lower bound on the number of vertices of an $h$-edge cut of $Q_n$ and obtain some consequences.

An important tool for the execution of parallel algorithms and the simulation of interconnection networks is graph embedding. The quality of an embedding can be assessed using some cost metrics. The dilation and wirelength are the commonly used parameters. The Knödel graph $W_{\mathrm{\Delta },n}$ is a minimum linear gossip network and has minimum broadcasting. It has $n$ vertices, $\frac{n\mathrm{\Delta }}{2}$ edges, where $n$ is even, and $1\le \mathrm{\Delta }\le \lfloor$log${}_{2}n\rfloor$. In this study, we solve the dilation problem of embedding the Knödel graph into certain cube-like architectures such as hypercube, folded hypercube, and augmented cube. In [G. Fertin, A. Raspaud, A survey on Knödel graphs, Discrete Applied Mathematics 137 (2004) 173–195], it is proved that the dilation of embedding the Knödel graph $W_{\mathrm{\Delta },2^{\mathrm{\Delta }}}$ into the hypercube $Q_{\mathrm{\Delta }}$ is at most $4$. In this study, we obtain an improved upper bound for dilation of embedding the Knödel graph into the hypercube and it is equal to $3$. Also, we calculate the wirelength of embedding the Knödel graph into the above-said cube-like architectures using dilation.