2 RESULTS ON LINEAR EMBEDDINGS OF COMPLETE BINARY-TREES

Given a binary tree T with n vertices, we want to embed T onto a given set A of n points on the line so as to minimize the total embedded ed ge length. Polynomial-time algorithms for the two following special ca ses of this problem can be found in the literature: (1) when T is arbi trary but A={1...n}; (2) when T is a complete binary tree and A is arb itrary. To the best of our knowledge, the complexity of the general pr oblem is open. In this paper we deal with case (2). Bern et al. presen ted an algorithm for this case that runs in time O(n(5.76)) and uses O (n(3.2)) space. They also considered the naive embedding, which maps t he root r of T into the middle point a of A, and then embeds, recursiv ely, the left and right subtrees of r to the left and right of a, resp ectively. This is equivalent to embedding T from left to right accordi ng to the inorder traversal. They prove that this naive algorithm appr oximates the optimal solution within the factor of 3. The main results of this paper are: (i) the proof that the approximation ratio of this naive algorithm is exactly 7/3, and (ii) a more efficient algorithm f or computing minimum embeddings of complete binary trees. Our algorith m runs in time O(n(1+log) 3)=O(n(2.59)), and uses O(n) space, where O( f)=O(flog(c)n), for some constant c>0.