Bandwidth minimization for Caterpillar graph

numerical analysis and hardware architecture. BMP on caterpillar graph is of particular interest then since it is related to the multi-processor scheduling.
In this work, we analysed the bandwidth minimization for the caterpillar graph. We define the constrained bush bandwidth problem and proved that it is NP-hard. Later, we proposed the labeling scheme which gives the best possible approximation result of additive factor 1. Then we defined the Shortest Distance Root Label finding problem and proposed a polynomial time exact algorithm to solve it.
We also analyzed the algorithm proposed by Haralabidas et. al. (HMM) for labeling caterpillar graphs and proposed an algorithm which can be proved to perform at least as good as HMM algorithm but gave constant
approximation of 2 for the proposed tight examples (respectively log n).