Scientific Research

An Academic Publisher

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

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

Share and Cite:

I. 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.Conflicts of Interest

The authors declare no conflicts of interest.

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

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.