Embedding of Binomial Trees in Locally Twisted Cubes with Link Faults

Abstract:

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, binomial tree embeddings in locally twisted cubes are studied. We present two major results in this paper: (1) For any integer n ≥ 2, an n-dimensional binomial tree B_n can be embedded in LTQ_n with dilation 1 by randomly choosing any vertex in LTQ_n as the root. (2) For any integer n ≥ 2, an n-dimensional binomial tree B_n can be embedded in LTQ_n with up to n − 1 faulty links in log(n − 1) steps where dilation = 1. The results are optimal in the sense that the dilations of all embeddings are 1.

• Periodical: Advanced Materials Research (Volumes 1049-1050)
• Pages: 1736-1740
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1049-1050.1736
• Online since: October 2014
• Authors: Lan Tao You*
• Keywords: Binomial Tree, Interconnection Network, Locally Twisted Cube, Parallel Computing

References

[1] P. Cull, S.M. Larson, The Möius cubes, IEEE Trans. Comput, 44 (5) (1995) 647–659.

DOI: 10.1109/12.381950

[2] K. Efe, A variation on the hypercube with lower diameter, IEEE Trans. Comput, 40 (11) (1991) 1312–1316.

DOI: 10.1109/12.102840

[3] P.A.J. Hilbers, M.R.J. Koopman, J.L.A. van de Snepscheut, The twisted cubes, in Parallel Architectures and Languages Europe, Lecture Notes in Computer Science, (1987) 152–159.

DOI: 10.1007/3-540-17943-7_126

[4] X. Yang, D.J. Evans, G.M. Megson, The locally twisted cubes, International Journal of Computer Mathematics, 82 (4) (2005) 401–413.

DOI: 10.1080/0020716042000301752

[5] X. Yang, D.J. Evans, G.M. Megson, Locally twisted cubes are 4-pancyclic. Applied Mathematics Letters, 17 (2004) 919–925.

DOI: 10.1016/j.aml.2003.10.009

[6] Y. Han, J. Fan, S. Zhang, J. Yang, P. Qian, Path Embedding in Faulty Locally Twisted Cubes, 2009 2nd IEEE International Conference on Computer Science and Information Technology (ICCSIT2009), (2009) 214–218.

DOI: 10.1109/iccsit.2009.5234748

[7] Y. Han, J. Fan, S. Zhang, J. Yang, P. Qian, Embedding meshes into locally twisted cubes, Information Sciences, 180 (2010) 3794–3805.

DOI: 10.1016/j.ins.2010.06.001

[8] T.L. Kung, Flexible cycle embedding in the locally twisted cube with nodes positioned at any prescribed distance, Information Sciences, 242 (2013) 92–102.

DOI: 10.1016/j.ins.2013.04.029

[9] Y.J. Liu, J.K. Lan, W.Y. Chou, C. Chen, Constructing independent spanning trees for locally twisted cubes, Theoretical Computer Science, 412 (2011) 2237–2252.

DOI: 10.1016/j.tcs.2010.12.061

[10] S. -Y. Hsieh, C. -J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science, 410 (2009) 926–932.

DOI: 10.1016/j.tcs.2008.12.025

[11] J. Wu, B. F. Eduardo, Y. Q. Luo, Embedding of Binomial Trees in Hypercubes with Link Faults, Journal of Parallel and Distributed Computing, 54 (1998) 59–74.

DOI: 10.1006/jpdc.1998.1482