Long paths and cycles in hypercubes with faulty vertices

A fault-free path in the n-dimensional hypercube Q_n with f faulty vertices is said to be long if it has length at least 2ⁿ-2f-2. Similarly, a fault-free cycle in Q_n is long if it has length at least 2ⁿ-2f. If all faulty vertices are from the same bipartite class of Q_n, such length is the best possible. We show that for every set of at most 2n-4 faulty vertices in Q_n and every two fault-free vertices u and v satisfying a simple necessary condition on neighbors of u and v, there exists a long fault-free path between u and v. This number of faulty vertices is tight and improves the previously known results. Furthermore, we show for every set of at most n²/10+n/2+1 faulty vertices in Q_n where n?15 that Q_n has a long fault-free cycle. This is a first quadratic bound, which is known to be asymptotically optimal.     

Longest fault-free paths in hypercubes with vertex faults

The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This study demonstrates that when f ? n − 2, the n-cube contains a fault-free path with length at least 2ⁿ − 2f − 1 (or 2ⁿ − 2f − 2) between two arbitrary vertices of odd (or even) distance. Since an n-cube is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the connectivity of an n-cube is n, the n-cube cannot tolerate n − 1 faulty vertices. Hence, our result is optimal.     

Long paths in hypercubes with conditional node-faults

Let F be a set of f?2n-5 faulty nodes in an n-cube Q_n such that every node of Q_n still has at least two fault-free neighbors. Then we show that Q_n-F contains a path of length at least 2ⁿ-2f-1 (respectively, 2ⁿ-2f-2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2ⁿ-2f-1 (or 2ⁿ-2f-2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n-2 faulty nodes are considered.     

Many-to-many disjoint paths in faulty hypercubes

This paper considers the problem of many-to-many disjoint paths in the hypercube Q_n with f_v faulty vertices and f_e faulty edges, and obtains the following result. For any integer k with 1?k?n-1, any two sets S and T of k fault-free vertices in different parts, if f_v+f_e?n-k-1, then there exist k disjoint fault-free (S,T)-paths in Q_n which contains at least 2ⁿ-2f_v vertices. This result is optimal in the worst case.     

Hamiltonian paths and cycles passing through a prescribed path in hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. In this paper, the following result is obtained: The n-dimensional hypercube Qn with n?3 is (2n−3)-path bipancyclic but is not (2n−2)-path bipancyclic, moreover, a path P of length k with 2?k?2n−3 lies in a cycle of length 2k−2 if and only if P contains two edges of the same dimension. In order to prove the above result we first show that any path of length at most 2n−1 is a subpath of a Hamiltonian path in Qn with n?2, moreover, the upper bound 2n−1 is sharp when n?4.     

Embedding paths of variable lengths into hypercubes with conditional link-faults

Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q_n, in which every node is still incident to at least two fault-free links. Then we show that Q_n-F has a path of any odd (resp. even) length in the range from the distance to 2ⁿ-1 (resp. 2ⁿ-2) between two arbitrary nodes even if |F|=2n-5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults.     

An efficient construction of one-to-many node-disjoint paths in folded hypercubes

A folded hypercube is basically a hypercube with additional links augmented, where the additional links connect all pairs of nodes with longest distance in the hypercube. In an n$n$-dimensional folded hypercube, it has been shown that n+1$n+1$ node-disjoint paths from one source node to other n+1$n+1$ (mutually) distinct destination nodes, respectively, can be constructed in O(n⁴)$O\left(n^4\right)$ time so that their maximal length is not greater than ⌈n/2⌉+1$\lceil n/2\rceil +1$, where n+1$n+1$ is the connectivity and ⌈n/2⌉$\lceil n/2\rceil$ is the diameter. Besides, their maximal length is minimized in the worst case. In this paper, we further show that by minimizing the computations of minimal routing functions, these node-disjoint paths can be constructed in O(n³)$O\left(n^3\right)$ time, which is more efficient, and is hard to be reduced because it must take O(n³)$O\left(n^3\right)$ time to compute a minimal routing function by solving a corresponding maximum weighted bipartite matching problem with the best known algorithm.     

On path bipancyclicity of hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. Based on Lemma 5, the authors of [C.-H. Tsai, S.-Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93-97] showed that the n-cube Qn with n?3 is (2n−4)-path bipancyclicity. In this paper, counterexamples to the lemma are given, therefore, their proof fails. And we show the following result: The n-cube Qn with n?3 is (2n−4)-path bipancyclicity but is not (2n−2)-path bipancyclicity, moreover, and a path P of length k with 2?k?2n−4 lies in a cycle of length 2k−2 if and only if P contains two edges of dimension i for some i, 1?i?n. We conjecture that if 2n−4 is replaced by 2n−3, then the above result also holds.     

On embedding subclasses of height-balanced trees in hypercubes

A height-balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the heights of the subtrees, rooted at the left and right child of v, differ by at most one; this difference is called the balance factor of v. These trees are extensively used as data structures for sorting and searching. We embed several subclasses of height-balanced trees of height h in Q_h+1 under certain conditions. In particular, if a tree T is such that the balance factor of every vertex in the first three levels is arbitrary (0 or 1) and the balance factor of every other vertex is zero, then we prove that T is embeddable in its optimal hypercube with dilation 1 or 2 according to whether it is balanced or not.     

Cycles embedding in hypercubes with node failures

The hypercube has been widely used as the interconnection network in parallel computers. The n-dimensional hypercube Qn is a graph having n² vertices each labeled with a distinct n-bit binary strings. Two vertices are linked by an edge if and only if their addresses differ exactly in the one bit position. Let fv denote the number of faulty vertices in Qn. For n?3, in this paper, we prove that every fault-free edge and fault-free vertex of Qn lies on a fault-free cycle of every even length from 4 to n²−2fv inclusive even if fv?n−2. Our results are optimal.     

A dynamic programming algorithm for simulation of a multi-dimensional torus in a crossed cube

The torus is a popular interconnection topology and several commercial multicomputers use a torus as the basis of their communication network. Moreover, there are many parallel algorithms with torus-structured and mesh-structured task graphs have been developed. If one network can embed a mesh or torus network, the algorithms with mesh-structured or torus-structured can also be used in this network. Thus, the problem of embedding meshes or tori into networks is meaningful for parallel computing. In this paper, we prove that for n ? 6 and 1 ? m ? ⌈n/2⌉ − 1, a family of 2^m disjoint k-dimensional tori of size 2^s₁×2^s₂×?×2^s_k each can be embedded in an n-dimensional crossed cube with unit dilation, where each s_i ? 2, , and max_1?i?k{s_i} ? 3 if n is odd and ; otherwise, max_1?i?k{s_i} ? n − 2m − 1. A new concept, cycle skeleton, is proposed to construct a dynamic programming algorithm for embedding a desired torus into the crossed cube. Furthermore, the time complexity of the algorithm is linear with respect to the size of desired torus. As a consequence, a family of disjoint tori can be simulated on the same crossed cube efficiently and in parallel.     

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].     

Fault-free cycles in folded hypercubes with more faulty elements

Let FFv (respectively, FFe) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional folded hypercube FQn. In this paper, we show that FQn−FFv−FFe contains a fault-free cycle with length at least n²−2|FFv| if |FFe|+|FFv|?2n−4 and |FFe|?n−1, where n?3. Our result improves the previously known result of [S.-Y. Hsieh, A note on cycle embedding in folded hypercubes with faulty elements, Information Processing Letters (2008), in press, doi:10.1016/j.ipl.2008.04.003] where |FFe|+|FFv|?n−1 and n?4.     

Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position

Assume that n is a positive integer with n?2. It is proved that between any two different vertices x and y of Qn there exists a path Pl(x,y) of length l for any l with h(x,y)?l?n²−1 and 2|(l−h(x,y)). We expect such path Pl(x,y) can be further extended by including the vertices not in Pl(x,y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Qn, for any vertex y∈V(Qn)−{x,z}, and for any integer l with h(x,y)?l?n²−1−h(y,z) and 2|(l−h(x,y)), there exists a hamiltonian path R(x,y,z;l) from x to z such that dR(x,y,z;l)(x,y)=l. Moreover, for any two distinct vertices x and y of Qn and for any integer l with h(x,y)?l?²n−1 and 2|(l−h(x,y)), there exists a hamiltonian cycle S(x,y;l) such that dS(x,y;l)(x,y)=l.     

Disjoint paths in hypercubes with prescribed origins and lengths

Given (i) any k vertices u ₁, u ₂, …, u _k (1≤k<n) in the n-cube Q _n , where (u ₁, u ₂), (u ₃, u ₄), …, (u _2m?1, u _2m ) (m≤? k\2 ?) are edges of the same dimension, (ii) any k positive integers a ₁, a ₂, …, a _k such that a ₁, a ₂, …, a _2m are odd and a _2m+1, …, a _k are even, with a ₁+a ₂+···+a _k =2 ⁿ , and (iii) k subsets W ₁, W ₂, …, W _k of V(Q _n ) with |W _i |≤n?k and if a _i =1, then u _i ¬∈W _i , for 1≤i≤k, we show that there exist k vertex-disjoint paths P ₍₁₎, P ₍₂₎, …, P _(k) in Q _n where P _(i) contains a _i vertices, its origin is u _i , and its terminus is in V(Q _n )/ W _i , for 1≤i≤k. We also prove a similar result which extends two well-known results of Havel, [I. Havel On hamilton circuits and spanning trees of hypercubes, ?asopis pro P?stování Matematiky, 109 (1984), pp. 135–152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705–712].     

Progressive accommodation of parametric faults in linear quadratic control

In this paper, a strategy based on the linear quadratic design, which progressively accommodates the feedback control law, is proposed. It significantly reduces the loss of performance that results from the time delay needed by fault accommodation algorithms to provide a solution. An aircraft example is given to illustrate the efficiency of progressive accommodation.     

Unicast in hypercubes with large number of faulty nodes

Unicast in computer/communication networks is a one-to-one communication between a source node s and a destination node t. We propose three algorithms which find a nonfaulty routing path between s and t for unicast in the hypercube with a large number of faulty nodes. Given the n-dimensional hypercube H_n and a set F of faulty nodes, node uϵ H_n is called k-safe if u has at least k nonfaulty neighbors. The H_n is called k-safe if every node of H_n is k-safe. It has been known that for 0⩽k⩽n/2, a k-safe H_n is connected if |F|⩽2^k(n-k)-1. Our first algorithm finds a nonfaulty path of length at most d(s,t)+4 in O(n) time for unicast between 1-safe s and t in the H_n with |F|⩽2n-3, where d(s,t) is the distance between s and t. The second algorithm finds a nonfaulty path of length at most d(s,t)+6 in O(n) time for unicast in the 2-safe H_n with |F|⩽4n-9. The third algorithm finds a nonfaulty path of length at most d(s,t)+O(k²) in time O(|F|+n) for unicast in the k-safe H_n with |F|⩽2^k(n-k)-1 (0⩽k⩽n/2). The time complexities of the algorithms are optimal. We show that in the worst case, the length of the nonfaulty path between s and t in a k-safe H_n with |F|⩽2^k(n-k)-1 is at least d(s,t)+2(k+1) for 0⩽k⩽n/2. This implies that the path lengths found by the algorithms for unicast in the 1-safe and 2-safe hypercubes are optimal     

Maximum number of edges joining vertices on a cube

Let E_d(n) be the number of edges joining vertices from a set of n vertices on a d-dimensional cube, maximized over all such sets. We show that E_d(n)=∑_i=0^r−1(l_i/2+i)2^l_i, where r and l₀>l₁>?>l_r−1 are nonnegative integers defined by n=∑_i=0^r−12^l_i.     

Shortest paths in euclidean graphs

We analyze a simple method for finding shortest paths inEuclidean graphs (where vertices are points in a Euclidean space and edge weights are Euclidean distances between points). For many graph models, the average running time of the algorithm to find the shortest path between a specified pair of vertices in a graph withV vertices andE edges is shown to beO(V) as compared withO(E +V logV) required by the classical algorithm due to Dijkstra.Support for the first author was provided in part by NSF Grant MCS-83-08806. Support for the second author was provided in part by NSF Grants MCS-81-05324 and DCR-84-03613, an NSF Presidential Young Investigator Award, an IBM research contract, and an IBM Faculty Development Award. Support for this research was also provided in part by an ONR and DARPA under Contract N00014-83-K-0146 and ARPA Order No. 4786. Equipment support was provided by NSF Grant MCS-81-218106.