Indhumathi raman

Fulltext

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

Certain height-balanced subtrees of hypercubes

International Journal of Computer Mathematics: Computer Systems Theory

A height-balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the heights of the left and right subtrees of v, differ by at most one. In this paper, we embed two subclasses of height-balanced trees into hypercubes with unit dilation. We also prove that for certain values of p and for all m≥1, a complete pm-ary tree of height h is embeddable into a hypercube of dimension O(mh) with dilation O(m) using the embedding results of the above height-balanced trees. These results improve and extend the results of Gupta et al. (2003) [10]. © 2013 Elsevier B.V.

Journal of Discrete Algorithms

Embedding certain height-balanced trees and complete pm-ary trees into hypercubes

A height balanced tree is a rooted binary tree T in which for every vertex v ∈ V(T), the difference bT (v) between the heights of the subtrees, rooted at the left and right child of v is at most one. We show that a height-balanced tree Th of height h is a subtree of the hypercube Qh+1 of dimension h + 1, if Th contains a path P from its root to a leaf such that bTh(v) = 1, for every non-leaf vertex v in P. A Fibonacci tree Fh is a height balanced tree Th of height h in which bFh(v) = 1, for every non-leaf vertex. F h has f(h + 2) - 1 vertices where f(h + 2) denotes the (h + 2)th Fibonacci number. Since f(h) ∼ 20.694h, it follows that if F h is a subtree of Qn, then n is at least 0.694(h+2). We prove that Fh is a subtree of the hypercube of dimension approximately 0.75h. © 2008 Korean Society for Computational and Applied Mathematics.

Journal of Applied Mathematics and Computing

Embedding height balanced trees and Fibonacci trees in hypercubes

A height-balanced tree is a rooted binary tree T in which for every vertex v ∈ V (T), the heights of the subtrees, rooted at the left and right child of v, differ by at most one; this difference is called the balance factor of v. These trees are extensively used as data structures for sorting and searching. We embed several subclasses of height-balanced trees of height h in Qh + 1 under certain conditions. In particular, if a tree T is such that the balance factor of every vertex in the first three levels is arbitrary (0 or 1) and the balance factor of every other vertex is zero, then we prove that T is embeddable in its optimal hypercube with dilation 1 or 2 according to whether it is balanced or not. © 2009 Elsevier Inc. All rights reserved.

Journal	International Journal of Computer Mathematics: Computer Systems Theory
Publisher	Informa UK Limited
ISSN	2379-9927
Open Access	Yes