共查询到20条相似文献,搜索用时 15 毫秒
1.
Embedding meshes into locally twisted cubes 总被引:1,自引:0,他引:1
As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQn(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2n−1 mesh can be embedded in LTQn with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2n−3 meshes can be embedded in LTQn with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4 × (2n−2 − 1) mesh can be embedded in LTQn with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2n−1 mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes. 相似文献
2.
The twisted cube is an important variant of the most popular hypercube network for parallel processing. In this paper, we consider the problem of embedding multi-dimensional meshes into twisted cubes in a systematic way. We present a recursive method for embedding a family of disjoint multi-dimensional meshes into a twisted cube with dilation 1 and expansion 1. We also prove that a single multi-dimensional mesh can be embedded into a twisted cube with dilation 2 and expansion 1. Our work extends some previously known results. 相似文献
3.
Chia-Jui Lai 《Information Processing Letters》2008,108(5):326-330
The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. The twisted cube is an important variation of the hypercube. Let TQn denote the n-dimensional twisted cube. In this paper, we consider embedding a family of 2-dimensional meshes into a twisted cube. The main results obtained in this paper are: (1) For any odd integer n?1, there exists a mesh of size 2×2n−1 that can be embedded in the TQn with unit dilation and unit expansion. (2) For any odd integer n?5, there exists a mesh of size 4×2n−2 that can be embedded in the TQn with dilation 2 and unit expansion. (3) For any odd integer n?5, a family of two disjoint meshes of size 4×2n−3 can be embedded into the TQn with unit dilation and unit expansion. Results (1) and (3) are optimal in the sense that the dilations and expansions of the embeddings are unit values. 相似文献
4.
Ruo-Wei Hung 《Theoretical computer science》2011,412(35):4747-4753
The n-dimensional hypercube network Qn is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional locally twisted cube LTQn, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as Qn. One advantage of LTQn is that the diameter is only about half of the diameter of Qn. Recently, some interesting properties of LTQn have been investigated in the literature. The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the interconnection network. The existence of two edge-disjoint Hamiltonian cycles in locally twisted cubes has remained unknown. In this paper, we prove that the locally twisted cube LTQn with n?4 contains two edge-disjoint Hamiltonian cycles. Based on the proof of existence, we further provide an O(n2n)-linear time algorithm to construct two edge-disjoint Hamiltonian cycles in an n-dimensional locally twisted cube LTQn with n?4, where LTQn contains 2n nodes and n2n−1 edges. 相似文献
5.
《国际计算机数学杂志》2012,89(8):1595-1602
Twisted cubes are an important class of hypercube-variant interconnection networks for parallel computing. In this paper, we evaluate the fault-tolerant mesh/torus embedding abilities of twisted cubes. By reducing the fault-tolerant mesh/torus embedding problem to the fault-tolerant pancyclicity, we propose several schemes for embedding meshes/tori in faulty twisted cubes. The obtained results reveal another appealing fault-tolerant feature of twisted cubes. 相似文献
6.
Crossed cubes are important variants of hypercubes. In this paper, we consider embeddings of meshes in crossed cubes. The major research findings in this paper are: (1) For any integer n ? 1, a 2 × 2n−1 mesh can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2n−3 meshes can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 2. The obtained results are optimal in the sense that the dilations of the embeddings are 1. The embedding of the 2 × 2n−1 mesh is also optimal in terms of expansion because it has the smallest expansion 1. 相似文献
7.
The twisted cube TQn is an alternative to the popular hypercube network. Recently, some interesting properties of TQn were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let fe and fv be the numbers of faulty edges and faulty vertices in TQn, respectively. We show that, with fe + fv ? n − 2, a faulty TQn still contains a cycle of length l for every 4 ? l ? ∣V(TQn)∣ − fv and odd integer n ? 3. 相似文献
8.
Weibei FAN Jianxi FAN Zhijie HAN Peng LI Yujie ZHANG Ruchuan WANG 《Frontiers of Computer Science》2021,15(3):153104
The foundation of information society is computer interconnection network, and the key of information exchange is communication algorithm. Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols. Nowadays, people can build complex interconnection networks by using very large scale integration (VLSI) technology. Locally exchanged twisted cubes, denoted by (s + t + 1)-dimensional LeTQs,t, which combines the merits of the exchanged hypercube and the locally twisted cube. It has been proved that the LeTQs,t has many excellent properties for interconnection networks, such as fewer edges, lower overhead and smaller diameter. Embeddability is an important indicator to measure the performance of interconnection networks. We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQs,t − ( fv + fe), with faulty vertices fv and faulty edges fe. Firstly, we prove that an LeTQs,t can tolerate up to s−1 faulty vertices and edges when embedding a Hamiltonian cycle, for s≥2, t≥3, and s≤t. Furthermore, we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQs,twith up to (s − 2) faulty vertices and edges. That is, we show that LeTQs,t is (s−1)-Hamiltonian and (s−2)- Hamiltonian-connected. The results are proved to be optimal in this paper with at most (s − 1)-fault-tolerant Hamiltonicity and (s − 2) fault-tolerant Hamiltonian connectivity of LeTQs,t. 相似文献
9.
Pao-Lien Lai 《Information Sciences》2011,181(23):5321-5332
The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. An n-dimensional twisted cube, TQn, is an important variation of the hypercube Qn and preserves many of its desirable properties. The problem of embedding linear arrays and cycles into a host graph has attracted substantial attention in recent years. The geodesic cycle embedding problem is for any two distinct vertices, to find all the possible lengths of cycles that include a shortest path joining them. In this paper, we prove that TQn is geodesic 2-pancyclic for each odd integer n ? 3. This result implies that TQn is edge-pancyclic for each odd integer n ? 3. Moreover, TQn × K2 is also demonstrated to be geodesic 4-pancyclic. 相似文献
10.
The n-dimensional locally twisted cube LTQn is a new variant of the hypercube, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of LTQn, and shows that if LTQn (n ? 3) contains at most n − 3 faulty vertices and/or edges then, for any fault-free edge e and any integer ? with 6 ? ? ? 2n − fv, there is a fault-free cycle of length ? containing the edge e, where fv is the number of faulty vertices. The result is optimal in some senses. The proof is based on the recursive structure of LTQn. 相似文献
11.
12.
Independent spanning trees on twisted cubes 总被引:1,自引:0,他引:1
Yan WangAuthor Vitae Jianxi FanAuthor Vitae Guodong ZhouAuthor VitaeXiaohua JiaAuthor Vitae 《Journal of Parallel and Distributed Computing》2012,72(1):58-69
Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There are two versions of the n independent spanning trees conjecture. The vertex (edge) conjecture is that any n-connected (n-edge-connected) graph has n vertex-independent spanning trees (edge-independent spanning trees) rooted at an arbitrary vertex. Note that the vertex conjecture implies the edge conjecture. The vertex and edge conjectures have been confirmed only for n-connected graphs with n≤4, and they are still open for arbitrary n-connected graph when n≥5. In this paper, we confirm the vertex conjecture (and hence also the edge conjecture) for the n-dimensional twisted cube TQn by providing an O(NlogN) algorithm to construct n vertex-independent spanning trees rooted at any vertex, where N denotes the number of vertices in TQn. Moreover, all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n≥2. 相似文献
13.
14.
Ming-Chien Yang Author Vitae 《Information Sciences》2010,180(20):4075-1263
The use of edge-disjoint spanning trees or independent spanning trees in a network for data broadcasting has the benefits of increased of bandwidth and fault-tolerance. In this paper, we propose an algorithm which constructs n edge-disjoint spanning trees in the n-dimensional twisted cube, denoted by TQn. Because the n-dimensional twisted cube is n-regular, the result is optimal with respect to the number of edge-disjoint spanning trees constructed. Furthermore, we also show that of the n edge-disjoint spanning trees constructed are independent spanning trees. This algorithm runs in time O(N log N) and can be parallelized to run in time O(log N) where N is the number of nodes in TQn. 相似文献
15.
《国际计算机数学杂志》2012,89(9):1863-1873
The n-dimensional locally twisted cube LTQn is a promising alternative to the hypercube because of its great properties. Not only is LTQn n-connected, but also meshes, torus, and edge-disjoint Hamiltonian cycles can embed in it. Ma and Xu [Panconnectivity of locally twisted cubes, Appl. Math. Lett. 19 (2006), pp. 681–685] investigated the panconnectivity of LTQn for flexible routing. In this paper, we combine panconnectivity with Hamiltonian connectedness to define Hamiltonian r-panconnectedness: a graph G of m vertices, m≥3, is Hamiltonian r-panconnected if for any three distinct vertices x, y, and z of G there exists a Hamiltonian path P of G such that P(1)=x, P(l+1)=y, and P(m)=z for every r≤l≤m?1?r, where P(i) denotes the ith vertex of P for 1≤i≤m. Then, we show that LTQn is Hamiltonian n-panconnected for n≥5. This property admits the path embedding via an intermediate node at any prescribed position, and our result achieves an improvement over that of Ma and Xu. 相似文献
16.
《国际计算机数学杂志》2012,89(6):728-740
The n-dimensional twisted cube, denoted by TQ n , a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, we show that every vertex in TQ n lies on a fault-free cycle of every length from 6 to 2 n , even if there are up to n?2 link faults. We also show that our result is optimal. 相似文献
17.
The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let TQn(V,E) denote the n-dimensional twisted cube. We prove that a path of length l can be embedded between any two distinct nodes with dilation 1 for any faulty set F⊂V(TQn)∪E(TQn) with |F|?n-3 and any integer l with 2n-1-1?l?|V(TQn-F)|-1 (n?3). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l and faulty set size |F| for a successful embedding are tight. That is, the result does not hold if l?2n-1-2 or |F|?n-2. We also extend the result on (n-3)-Hamiltonian connectivity of TQn in the literature. 相似文献
18.
A grid (or a mesh) is a two-dimensional permutation: an m× n-grid of size mn is an m× n-matrix where the entries run through the elements {1,2, …, mn}. We prove that if δ1 and δ2 are any two linear orders on {1,2, …, N}, then they can be simultaneously embedded (in a well defined sense) into a unique grid having the smallest size. 相似文献
19.
Yi-Jiun LiuJames K. Lan Well Y. ChouChiuyuan Chen 《Theoretical computer science》2011,412(22):2237-2252
The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQn. The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQn. However, we find out that LTQn is not vertex-transitive when n≥4; therefore Hsieh and Tu’s result does not solve the Edge Conjecture for LTQn. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQn; consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQn. 相似文献