Graph bandwidth of weighted caterpillars

Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars. More specifically, we show that the GBM problem of caterpillars with hair-length at most 2 and the GBM problem of star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an O(n log n log(nw_max))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and w_max is the maximum edge weight. For caterpillars with hair-length at most k, we give a k-approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of log(2n) of the lower bound.