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.     

Path partitions of hypercubes

A path partition of a graph G is a set of vertex-disjoint paths that cover all vertices of G. Given a set of pairs of distinct vertices of the n-dimensional hypercube Qn, is there a path partition of Qn such that ai and bi are endvertices of Pi? Caha and Koubek showed that for 6m?n, such a path partition exists if and only if the set P is balanced in the sense that it contains the same number of vertices from both classes of bipartition of Qn.In this paper we show that this result holds even for 2m−e<n, where e is the number of pairs of P that form edges of Qn. Moreover, our bound is optimal in the sense that for every n?3, there is a balanced set P in Qn such that 2m−e=n, but no path partition with endvertices prescribed by P exists.     

A multiperiod set covering location model for dynamic redeployment of ambulances

Emergency medical service (EMS) providers continually seek ways to improve system performance particularly the response time to incidents. The demand for ambulances fluctuate throughout the week, depending on the day of week, and even the time of day, therefore EMS operators can improve system performance by dynamic relocation/redeployment of ambulances in response to fluctuating demand patters. The objective of the model is to determine the minimum number of ambulances and their locations for each time cluster in which significant changes in demand pattern occur while meeting coverage requirement with a predetermined reliability. The model is further enhanced by calculating ambulance specific busy probabilities and validated by a comprehensive simulation model. Computational results on experimental data sets and data from an EMS agency are provided.     

Efficient realization of frequently used bijections on cube-connected cycles

CCC has lower hardware complexity than hypercube and is suited for current VLSI technology.LC-permutations are a large set of important permutations frequently used in various parallel computations.Existing routing algorithms for CCC cannot realize LC-permutations without network conflict.We present an algorithm to realize LC-permutations on CCC.The algorithm consists of two periods of inter-cycle transmissions and one period of inner-cycle transmissions.In the inter-cycle transmissions the dimensional links of CCC are used in a “pipeline” manner and in the inner-cycle transmissions the data packets are sorted by a part of its destination address.The algorithm is fast (O(log2N)) and no conflict will occur.     

Railcar reallocation optimization on water-rail network under uncertain busyness

Water-rail intermodal transportation can reduce cargo losses and transportation transferring costs. However, the imbalance between the capacity of the scheduled railway network and the large container freight demand greatly reduces operational efficiency. To minimize the total transportation cost and relocation cost, a railcar reallocation stochastic optimization model is formulated to deal with uncertain congestion in the railway network. To capture the uncertain busyness and queuing pattern, a hypercube spatial queue model is embedded in the optimization model by estimating the expected queue length and waiting time. To solve the proposed nonlinear nonconcave stochastic model, an approximate hypercube based iterative algorithm is proposed. A real-world case study is presented to show the effectiveness and efficiency of the proposed method. The proposed model outperforms the comparable deterministic model in the objective value. Sensitivity analyses on the ratio of the unit waiting cost and the unit travel cost for empty cars, and the total number of freight cars show the robustness of the proposed method.     

Hypercube sandwich approach to conferencing

This paper presents a novel cascaded conference network that provides distributed processing and signal transmission among members of disjoint sets of generic send/receive devices called conferees. It assumes an online request model in which idle groups of conferees may request the formation of a conference interconnection. Once a conference is established, all conferees remain connected until the entire conference is dissolved. The Hypercube Sandwich Network (HSN) consists of two components. A bidirectional permutation network is used for routing purposes to and from a hypercube of special processing elements for the purpose of conference formation. The HSN achieves strictly nonblocking performance for N conferees using O(Nlog N) processing elements, and this is shown to be tight to within a log ^1/4 N factor. Previous constructions required a quadratic number of processing elements for strictly nonblocking performance or could only provide wide-sense nonblocking conferencing. If the stronger requirement is made that the communication delay is logarithmic in the conference size, a simple algorithm is presented for wide-sense nonblocking conferencing in an HSN with O(N log N) processing elements.An earlier version of this paper was presented at the 1995 International Conference on Parallel Processing Techniques and Applications.     

Cycles passing through a prescribed path in a hypercube with faulty edges

Let Qn denote an n-dimensional hypercube with n?2, P be a path of length h in Qn and F⊂E(Qn)\E(P). Recently, Tsai proved that if 1?h?n−1 and |F|?n−1−h, then in the graph Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if |F|?h−2. In this paper, we show that if 1?h?2n−3 and |F|?n−2−⌊h/2⌋, then in Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if P contains two edges of the same dimension or P is a shortest path and |F∩E(Qh)|?h−2, where Qh is the h-dimensional subcube containing the path P. Moreover, the upper bound 2n−3 of h is sharp and the upper bound n−2−⌊h/2⌋ of |F| is sharp for any given h with 1?h?2n−3.     

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.     

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.     

Conditional edge-fault-tolerant Hamiltonicity of dual-cubes

The dual-cube is an interconnection network for linking a large number of nodes with a low node degree. It uses low-dimensional hypercubes as building blocks and keeps the main desired properties of the hypercube. A dual-cube DC(n) has n + 1 links per node where n is the degree of a cluster (n-cube), and one more link is used for connecting to a node in another cluster. In this paper, assuming each node is incident with at least two fault-free links, we show a dual-cube DC(n) contains a fault-free Hamiltonian cycle, even if it has up to 2n − 3 link faults. The result is optimal with respect to the number of tolerant edge faults.