Abstract
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] = {0,1,...,n-1}. 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 approximation 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(log3n) of the optimal bandwidth. In this paper, we present a simple randomized O(log2 n√log n)-approximation algorithm for bandwidth minimization on trees.
| Original language | English (US) |
|---|---|
| Pages | 788-793 |
| Number of pages | 6 |
| State | Published - 2000 |
| Event | 11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: Jan 9 2000 → Jan 11 2000 |
Other
| Other | 11th Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | San Francisco, CA, USA |
| Period | 1/9/00 → 1/11/00 |
ASJC Scopus subject areas
- Software
- General Mathematics