Bandwidth Minimization: An approximation algorithm for caterpillars

The Bandwidth Minimization Problem (BMP) is the problem, given a graphG and an integerk, to map the vertices ofG to distinct positive integers, so that no edge ofG has its endpoints mapped to integers that differ by more thank. There is no known approximation algorithm for this problem, even for the case of trees. We present an approximation algorithm for the BMP for the case of special graphs, called caterpillars. The BMP arises from many different engineering applications which try to achieve efficient storage and processing and has been studied extensively, especially with relation to other graph layout problems. In particular, the BMP for caterpillars is related to multiprocessor scheduling. It has been shown to be NP-complete, even for degree-3 trees. Our algorithm, gives a logn times optimal algorithm, wheren is the number of nodes of the caterpillar. It is based on the idea of level algorithms.This work has been, in part, supported by the Computer Learning Research (CLEAR) Center at UTD.