Approximation algorithms for the bandwidth minimization problem for a large class of trees

We present approximation algorithms for the bandwidth minimization problem (BMP) for a large class of trees. The BMP is NP-hard, even for trees of maximum node degree 3. The problem finds applications in many areas, including VLSI layout, multiprocessor scheduling, and matrix processing, and has been studied for both graphs and matrices. We study the problem on trees having the following property: given any tree nodev, the depth difference of any two nonempty subtrees rooted atv is bounded by a constantk. We call such treesh(k)trees orgeneralized height-balanced (GHB)trees. The above definition extends the class of balanced trees to trees with depthd=Θ(\N\). For any tree in the above defined class, anO (logd) times optimal algorithm is presented. Furthermore, we extend the application of the algorithm to trees that simulate theh(k) property, which we callh(k)-like trees, and also provide intuitive ideas for an approximation algorithm for general trees.