Embedding of tori and grids into twisted cubes

AbstractThe hypercube is one of the most popular interconnection networks since it has a simple structure and is easy to implement. An n-dimensional twisted cube, TQn, is an important variation of hypercube Qn and preserves many of its desirable properties. The problem of how to embed a family of disjoint meshes (or tori) into a host graph has attracted great attention in recent years. However, there is no systematic method proposed to generate the desired meshes and tori in TQn. In this paper, we develop two systematic linear time algorithms for embedding disjoint multi-dimensional tori into TQn, n≥7, as follows: (1) for a positive integer m with ⌊n2⌋≤m≤n−4, a family of 2m disjoint k-dimensional tori of size 2s1×2s2×⋯×2sk each can be embedded with unit dilation, where k≥2 and ∑i=1ksi≤n−m, and (2) for a positive integer m with 2≤m≤n−5, a family of 2m disjoint k-dimensional tori of size 2s1×2s2×⋯×2sk each can be embedded with unit dilation, where k≥2, si≥2, ∑i=1ksi≤n−m, and max1≤i≤k{si}≥n−2m. Moreover, we also provide similar embedding results for meshes and hypercubes. Our results mean that a family of torus-structured (mesh-structured, or hypercube-structured) parallel algorithms can be executed on the same twisted cube efficiently and in parallel