The hamiltonicity of generalized honeycomb torus networks

Yang et al. (2004) [8] proved that the generalized honeycomb torus GHT(m,n,d)$\mathit{GHT}(m,n,d)$ is hamiltonian, but their proofs are not sufficient when the width m   is odd. In this paper, we propose a series of procedures for constructing hamiltonian cycles in generalized honeycomb tori, which apply to every instance of GHT(m,n,d)$\mathit{GHT}(m,n,d)$ with odd width m.     

Generalized honeycomb torus is Hamiltonian

Generalized honeycomb torus is a candidate for interconnection network architectures, which includes honeycomb torus, honeycomb rectangular torus, and honeycomb parallelogramic torus as special cases. Existence of Hamiltonian cycle is a basic requirement for interconnection networks since it helps map a “token ring” parallel algorithm onto the associated network in an efficient way. Cho and Hsu [Inform. Process. Lett. 86 (4) (2003) 185-190] speculated that every generalized honeycomb torus is Hamiltonian. In this paper, we have proved this conjecture.     

Embedding a long fault-free cycle in a crossed cube with more faulty nodes

The crossed cube is an important variant of the most popular hypercube network for parallel computing. In this paper, we consider the problem of embedding a long fault-free cycle in a crossed cube with more faulty nodes. We prove that for n?5 and f?2n−7, a fault-free cycle of length at least n²−f−(n−5) can be embedded in an n-dimensional crossed cube with f faulty nodes. Our work extends some previously known results in the sense of the maximum number of faulty nodes tolerable in a crossed cube.     

A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges

In this paper, we consider the problem of a fault-free Hamiltonian cycle passing through prescribed edges in an n-dimensional hypercube Qn with some faulty edges. We obtain the following result: Let n?2, F⊂E(Qn), E₀⊂E(Qn)\F with 1?|E₀|?2n−3, |F|<n−(⌊|E₀|/2⌋+1). If the subgraph induced by E₀ is a linear forest (i.e., pairwise vertex-disjoint paths), then in the graph Qn−F all edges of E₀ lie on a Hamiltonian cycle.     

Generalized honeycomb torus

Stojmenovic introduced three different honeycomb tori by adding wraparound edges on honeycomb meshes, namely honeycomb rectangular torus, honeycomb rhombic torus, and honeycomb hexagonal torus. These honeycomb tori have been recognized as an attractive alternative to existing torus interconnection networks in parallel and distributed applications. In this paper, we propose generalized honeycomb tori. The three different honeycomb tori proposed by Stojmenovic are proved to be special cases of our proposed generalized honeycomb tori. We also discuss the Hamiltonian property of some generalized honeycomb tori.     

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 properties of twisted hypercube-like networks with more faulty elements

Twisted hypercube-like networks (THLNs) are a large class of network topologies, which subsume some well-known hypercube variants. This paper is concerned with the longest cycle in an n-dimensional (n-D) THLN with up to 2n−9 faulty elements. Let G be an n-D THLN, n≥7. Let F be a subset of V(G)?E(G), |F|≤2n−9. We prove that G−F contains a Hamiltonian cycle if δ(G−F)≥2, and G−F contains a near Hamiltonian cycle if δ(G−F)≤1. Our work extends some previously known results.     

Parallel algorithms for the hamiltonian cycle and hamiltonian path problems in semicomplete bipartite digraphs

We give anO(log⁴ n)-timeO(n ²)-processor CRCW PRAM algorithm to find a hamiltonian cycle in a strong semicomplete bipartite digraph,B, provided that a factor ofB (i.e., a collection of vertex disjoint cycles covering the vertex set ofB) is computed in a preprocessing step. The factor is found (if it exists) using a bipartite matching algorithm, hence placing the whole algorithm in the class Random-NC. We show that any parallel algorithm which can check the existence of a hamiltonian cycle in a strong semicomplete bipartite digraph in timeO(r(n)) usingp(n) processors can be used to check the existence of a perfect matching in a bipartite graph in timeO(r(n)+n ² /p(n)) usingp(n) processors. Hence, our problem belongs to the class NC if and only if perfect matching in bipartite graphs belongs to NC. We also consider the problem of finding a hamiltonian path in a semicomplete bipartite digraph.     

Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n-cube, denoted by , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n?2. We show that when |F|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal.     

Minimum neighborhood in a generalized cube

Generalized cubes are a subclass of hypercube-like networks, which include some hypercube variants as special cases. Let θG(k) denote the minimum number of nodes adjacent to a set of k vertices of a graph G. In this paper, we prove for each n-dimensional generalized cube and each integer k satisfying n+2?k?2n. Our result is an extension of a result presented by Fan and Lin [J. Fan, X. Lin, The t/k-diagnosability of the BC graphs, IEEE Trans. Comput. 54 (2) (2005) 176-184].     

Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

Let Wn denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Qn, and let S and T be any two sets of k vertices in different partite sets of Wn. In this paper, we show that the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn if and only if k=²n−1 or the graph Wn−(S∪T) has a perfect matching. Moreover, if the graph Wn−(S∪T) has a perfect matching M, then the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn and all edges in M. And some corollaries are given.     

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.     

Finding cycles in hierarchical hypercube networks

The hierarchical hypercube network, which was proposed as an alternative to the hypercube, is suitable for building a large-scale multiprocessor system. A bipartite graph G=(V,E) is bipancyclic if it contains cycles of all even lengths ranging from 4 to |V|. In this paper, we show that the hierarchical hypercube network is bipancyclic.     

Complete path embeddings in crossed cubes

Crossed cubes are popular variants of hypercubes. In this paper, we study path embeddings between any two distinct nodes in crossed cubes. We prove two important results in the n-dimensional crossed cube: (a) for any two nodes, all paths whose lengths are greater than or equal to the distance between the two nodes plus 2 can be embedded between the two nodes with dilation 1; (b) for any two integers n ? 2 and l with , there always exist two nodes x and y whose distance is l, such that no path of length l + 1 can be embedded between x and y with dilation 1. The obtained results are optimal in the sense that the dilations of path embeddings are all 1. The results are also complete, because the embeddings of paths of all possible lengths between any two nodes are considered.     

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r -正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。     

Embedding of Cycles in Twisted Cubes with Edge-Pancyclic

In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4≤l≤2 ⁿ , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2 ⁿ , and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n ²+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ _n for any (u,v)∈E(TQ _n ) and any integer l with 4≤l≤2 ⁿ .     

The generalized momentum approach to the dynamic modeling of a 6-dof parallel manipulator

Dynamic modeling is of great importance regarding computer simulation and advanced control of parallel manipulators. Due to their closed-loop structure and kinematic constraints, dynamic modeling of parallel manipulators presents an inherent complexity. Despite the intensive investigation in this topic of robotics, mostly conducted in the last 2 decades, additional research still has to be done in this area. The dynamic model of a parallel manipulator is usually developed using the Newton–Euler or the Lagrange methods. Nevertheless, additional approaches were also investigated, such as the virtual work, and screw theory based approaches. In this paper, an approach based on the manipulator generalized momentum is studied. This approach is used to obtain the dynamic model of a six degrees-of-freedom parallel manipulator. The involved computational effort is evaluated and compared with the one involved within the classic Lagrange’s formulation. It is showed the proposed approach presents a much lower computational burden.     

Embedding a family of disjoint 3D meshes into a crossed cube

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint 3D meshes into a crossed cube. Two major contributions of this paper are: (1) for n?4, a family of two disjoint 3D meshes of size 2×2×2^n-3 can be embedded in an n-D crossed cube with unit dilation and unit expansion, and (2) for n?6, a family of four disjoint 3D meshes of size 4×2×2^n-5 can be embedded in an n-D crossed cube with unit dilation and unit expansion. These results mean that a family of two or four 3D-mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends the results recently obtained by Fan and Jia [J. Fan, X. Jia, Embedding meshes into crossed cubes, Information Sciences 177(15) (2007) 3151-3160].     

Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks

This paper presents the evaluation of the solution quality of heuristic algorithms developed for scheduling multiprocessor tasks for a class of multiprocessor architectures designed to exploit temporal and spatial parallelism simultaneously. More specifically, we deal with multi-level or partitionable architectures where MIMD parallelism and multiprogramming support are the two main characteristics of the system. We investigate scheduling a number of pipelined multiprocessor tasks with arbitrary processing times and arbitrary processor requirements in this system. The scheduling problem consists of two interrelated sub-problems, which are finding a sequence of pipelined multiprocessor tasks on a processor and finding a proper mapping of tasks to the processors that are already being sequenced. For the solution of the second problem, various techniques are available. However, the problem remains of generating a feasible sequence for the pipelined operations. We employed three well-known local search heuristic algorithms that are known to be robust methods applicable to various optimization problems. These are Simulated Annealing, Tabu Search, and Genetic Algorithms. We then conduct computational experiments and evaluate the reduction achieved in completion time by each heuristic. We have also compared the results with well-known simple list-based heuristics.