On Embedding of m-Sequential k-ary Trees into Hypercubes

Indra Rajasingh, Bharati Rajan, Ramanathan Sundara Rajan
DOI: 10.4236/am.2010.16065                

Abstract

In this paper, we present an algorithm for embedding an m-sequential k-ary tree into its optimal hypercube with dilation at most 2 and prove its correctness.

Keywords

Hypercube, Embedding, Dilation, Pre-order Labeling, Hamiltonian Cycle, k-ary Tree

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Rottger and U. P. Schroeder, “Embedding of Hypercubes into Grids,” Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, Brno, 24-28 August 1998 , pp. 693-701.
[2]	S. L. Bezrukov, B. Monien, W. Unger and G. Wechsung, “Embedding Ladders and Caterpillars into the Hyper- cube,” Discrete Applied Mathematics, Vol. 83, No. 1-3, 1998, pp. 21-29.
[3]	P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, “Exact Wirelength of Hypercube on a Grid,” Discrete Applied Mathematics, Vol. 157, No. 7, 2009, pp. 1486-1495.
[4]	V. Sunitha, “Embedding Some Hierarchical Caterpillars into Hypercube,” Electronic Notes in Discrete Mathematics, Vol. 22, No. 10, 2005, pp. 387-389.
[5]	J. M. Xu, “Topological Structure and Analysis of Inter- connection Networks,” Kluwer Academic Publishers, Norwell, 2001.
[6]	S. A. Choudum and I. Raman, “Embedding Height Balanced Trees and Fibonacci Trees in Hypercubes,” Journal of Applied Mathematics and Computing, Vol. 30, No. 1-2, 2009, pp. 39-52.
[7]	S. N. Bhatt and I. C. Ipsen, “How to Embed Trees in Hypercubes,” Technical Report YALEU/DCS/RR-443, Yale University, Connecticut, 1985.
[8]	Q. Dong, X. Yang, J. Zhao and Y. Y. Tang,“Embedding a Family of Disjoint 3D Meshes into a Crossed Cube,” Infor- mation Sciences, Vol. 178, No. 11, 2008, pp. 2396-2405.
[9]	I. Havel, “On Hamiltonian Circuits and Spanning Trees of Hypercubes,” Casopis.Pest.Mat., Vol. 109, No. 2, 1984, pp. 135- 152.
[10]	I. Havel and P. Liebl, “O Vnoren Dichotomickeho Stromu Do Krychle (in Czech with English summary),” Casopis. Pest. Mat., Vol. 97 , No. 2, 1972, pp. 201-205.
[11]	L. Nebesky, “On Cubes and Dichotomic Trees,” Casopis. Pest. Mat., Vol. 99, No. 2, 1974, pp. 164-167.
[12]	D. E. Knuth, “The Art of Computer Programming-3, Sorting and Searching,” Addison-Wesley Publishing Company, Massachusetts, 1973.
[13]	T. Dvorák, I. Havel, P. Liebl and J.-M. Laborde, “Generalized Hypercubes and Graph Embedding with Dilation,” Rostocker Mathematisches Kolloquium, Vol. 39, 1990, pp. 13-20.
[14]	B. Monien and H. Sudborough, “Simulating Binary Trees on Hypercubes,”VLSI, Algorithms and Architectures, Proceedings of the 3rd Aegean Workshop on Computing, LNCS, Springer-Verlag Vol. 319, No. 24, 1988, pp. 170-180.
[15]	T. Dvo?ák, “Dense Sets and Embedding Binary Trees into Hypercubes,”Discrete Applied Mathematics, Vol. 155, No. 4, 2007, pp. 506-514.
[16]	V. Heun and E. W. Mayr, “A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube,”Journal of Algorithms, Vol. 20, No. 2, 1996, pp. 375-399.
[17]	V. Heun and E. W. Mayr, “Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes,” Journal of Parallel and Distributed Computing, Vol. 61, No. 8, 2001, pp. 1110-1125.
[18]	O. Egecioglu and M. Ibel, “Asymptotic Hypercube Embeddings of Dynamic k-ary Trees,” Congressus Numerantium, Vol. 126, 1997, pp. 21-32.
[19]	J. Fan and X. Jia, “Embedding Meshes into Crossed Cubes,”Information Sciences, Vol. 177, No. 15, 2007, pp. 3151-3160.
[20]	J. Fan, X. Jia and X. Lin,“Complete Path Embeddings in Crossed Cubes,”Information Sciences, Vol. 176, No. 22, 2006, pp. 3332-3346.
[21]	J. S. Fu,“Longest Fault-free Paths in Hypercubes with Vertex Faults,” Information Sciences, Vol. 176, No. 7, 2006, pp. 759-771.
[22]	I. Havel and P. Liebl,“One-legged Caterpillars Span Hypercubes,”Journal of Graph Theory, Vol. 10, No. 1 ,1986, pp. 69-77.
[23]	T. C. Lin and D. R. Duh, “Constructing Vertex-Disjoint Paths in (n, k)-star Graphs,”Information Sciences, Vol. 178, No. 3, 2008, pp. 788-801.
[24]	C. H. Tsai and Y. C. Lai, “Conditional Edge-Fault-Tolerant Edge-Bipancyclicity of Hypercubes,” Information Sciences, Vol. 177, No. 24, 2007, pp. 5590-5597.
[25]	R. Y. Wu, G. Chen, Y-L. Kuo and G. J. Chang,“Node- disjoint Paths in Hierarchical Hypercube Networks,”Information Sciences, Vol. 177, No. 19, 2007, pp. 4200-4207.
[26]	W. K. Chen and M. F. M. Stallmann,“On Embedding Binary Trees into Hypercubes,” Journal on Parallel and Distributed Computing, Vol. 24, No. 2, 1995, pp. 132-138.
[27]	I. Havel, “On Certain Trees in Hypercubes,” In Topics in Combinatorics and Graph Theory, Physica-Verlag, Heidelberg, 1990, pp. 353-358.
[28]	S. A. Choudum and I. Raman,“On Embedding Subclasses of Height-balanced Trees in Hypercubes,”Journal of Applied Mathematics, Vol. 179, No. 9, 2009, pp. 1333-1347.