The performance ability of a distributed multiprocessor is determined by its corresponding interconnection network and the primary criteria for choosing an appropriate interconnection network is its graph embedding capability. An embedding of a graph G into a graph H is an injective map on the vertices such that each edge of G is mapped into a shortest path of H. The wirelength of this embedding is the sum of the number of paths corresponding to G crossing every edge in H. In this paper we embed the locally twisted cube into rooted hypertrees to obtain the exact wirelength.

Emedding, locally twisted cube, rooted hypertree, wirelength

[1] Abraham, J., Arockiaraj, M., “Layout of embedding locally twisted cube into the extended theta mesh topology”, Vol 63, pp.371-379 , 2017.
[2] Abraham, J., Arockiaraj, M., “Wirelength of enhanced hypercubes into r-rooted complete binary trees”, Vol 53, pp.373-382 , 2016.
[3] Arockiaraj, M., Abraham, J., Quadras, J., Shalini, A.J.: “Linear layout of locally twisted cubes”. International Journal of Computer Mathematics. Vol 94, Issue.1, pp. 56-65, 2017
[4] Arockiaraj, M.,Rajasingh, I., Quadras, J., Shalini, A.J.: “Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees”.Discrete Optimization. Vol 17, pp.1-13 ,2015
[5] Bezrukov, S.L., Chavez, J.D., Harper, L.H., Rottger, M., Schroeder, U.-P.: “Embedding of hypercubes into grids”, Mathematical Foundations of Computer Science, Springer Berlin Heidelberg, 1998.
[6] Bezrukov, S.L., Chavez, J.D., Harper, L.H., Rottger, M., Schroeder, U.-P.: “The congestion of n-cube layout on a rectangular grid”, Discrete Mathematics. Vol 213, Issue.1,pp.13-19, 2000
[7] Harper, L.H.: “Global Methods of Combinatorial Isoperimetric Problems”. Cambridge University Press, 2004.
[8] Lai Y.L., Williams, K.: “A survey of solved problems and applications on bandwidth, edge sum and profile of graphs”. Journal of Graph Theory. Vol 31,pp. 75-94, 1999
[9] Manuel, P., Arockiaraj, M., Rajasingh, I., Rajan, B.: “ Embedding hypercubes into
cylinders, snakes and caterpillars for minimizing wirelength”. Discrete Applied Mathematics. Vol 159, Issue .17,pp. 2109-2116, 2011
[10] Manuel, P., Rajasingh, I., Rajan, B., Mercy, H.: “Exact wirelength of hypercube on a
Grid”. Discrete Applied Mathematics. Vol 157, Issue 7, pp. 1486-1495, 2009
[11] Opatrny, J., Sotteau, D.: “Embeddings of complete binary trees into grids and extended
grids with total vertex-congestion “.Discrete Applied Mathematics.Vol 98,pp. 237-254 , 2000
[12] Rajan, R.S., Manuel, P., Rajasingh, I.: “Embeddings between hypercubes and
Hypertrees”. Journal of Graph Algorithms and Applications. Vol 19,Issue.1,pp. 361-373, 2015
[13] Yang, X., Evans, D.J., Megson, G.M.: “The Locally Twisted Cubes”. International
Journal of Computer Mathematics. Vol 82, Issue.4 pp.401-413, 2005