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

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.

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.

Cite this paper

nullI. Rajasingh, B. Rajan and R. Rajan, "On Embedding of m-Sequential k-ary Trees into Hypercubes,"*Applied Mathematics*, Vol. 1 No. 6, 2010, pp. 499-503. doi: 10.4236/am.2010.16065.

nullI. Rajasingh, B. Rajan and R. Rajan, "On Embedding of m-Sequential k-ary Trees into Hypercubes,"

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.

[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.