Embedding a k-D Torus into a Locally Twisted Cube
Chia-Jui Lai, Chang‐Hsiung Tsai, Tseng-Kui Li · 2010
The locally twisted cube is one of the most notable variations of hypercube, but some properties of the locally twisted cube are superior to those of the hypercube. For example, the diameter of former is almost the half of that of the later. This paper addresses how to embed a maximal size of multi-dimensional torus into a locally twisted cube. The major contribution of this paper is that for n ≥4, every k-dimensional torus of size 2s1× 2s2× ⋯ × 2sksatisfyingΣi=1ksi= n can be embedded into an n-dimensional locally twisted cube with dilation two and unit expansion. Further, an embedding algorithm can be constructed based on our embedding method and the time complexity of the algorithms linear with respect to the size of the locally twisted cube. The embedding is optimal in the sense that it has unit expansion.