Research ArticleOpen AccessGoogle Scholar indexed
On Embedding of m-Sequential k-ary Trees into Hypercubes
- 1
- 2
- 3
Applied Mathematics·Volume 01 (2010)·Pages 499–503·Published 27 December 2010·DOI10.4236/am.2010.16065
Copy link · social · email
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.
KeywordsHypercubeEmbeddingDilationPre-order LabelingHamiltonian Cyclek-ary Tree
- 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.
- 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.
- 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.
- V. Sunitha, “Embedding Some Hierarchical Caterpillars into Hypercube,” Electronic Notes in Discrete Mathematics, Vol. 22, No. 10, 2005, pp. 387-389.
- J. M. Xu, “Topological Structure and Analysis of Inter- connection Networks,” Kluwer Academic Publishers, Norwell, 2001.
- 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.
- S. N. Bhatt and I. C. Ipsen, “How to Embed Trees in Hypercubes,” Technical Report YALEU/DCS/RR-443, Yale University, Connecticut, 1985.
- 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.
- I. Havel, “On Hamiltonian Circuits and Spanning Trees of Hypercubes,” Casopis.Pest.Mat., Vol. 109, No. 2, 1984, pp. 135- 152.
- 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.
- L. Nebesky, “On Cubes and Dichotomic Trees,” Casopis. Pest. Mat., Vol. 99, No. 2, 1974, pp. 164-167.
- D. E. Knuth, “The Art of Computer Programming-3, Sorting and Searching,” Addison-Wesley Publishing Company, Massachusetts, 1973.
- 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.
- 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.