APPROXIMATION ALGORITHMS FOR THE BANDWIDTH MINIMIZATION PROBLEM FOR ALARGE CLASS OF TREES

We present approximation algorithms for the bandwidth minimization pro blem (BMP) for a large class of trees. The BMP is NP-hard, even for tr ees of maximum node degree 3, The problem finds applications in many a reas, including VLSI layout, multiprocessor scheduling, and matrix pro cessing, and has been studied for both graphs and matrices. We study t he problem on trees having the following property: given any tree node nu, the depth difference of any two nonempty subtrees rooted at nu is bounded by a constant k. We call such trees h(k) trees or generalized height-balanced (GHB) trees, The above definition extends the class o f balanced trees to trees with depth d = Omega(\N\). For any tree in t he above defined class, an O(log d) times optimal algorithm is present ed. Furthermore, we extend the application of the algorithm to trees t hat simulate the h (k) property, which we call h(k)-like trees, and al so provide intuitive ideas for an approximation algorithm for general trees.