Improved bandwidth approximation for trees
Anupam Gupta · 2000
A linear arrangement of an n-vertex graph G = (V;E) is a one-one mapping f of the vertex set V onto the set [n] = f0; 1; : : : ; n1g. The bandwidth of this linear arrangement is the maximum distance between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known ap-proximation algorithm for the minimum bandwidth linear arrangement (which is based on the principle of volume respecting embeddings) outputs a linear arrangement which has bandwidth within O(log 3 n) of the optimal bandwidth. In this paper, we present a simple randomized O(log