Improved bandwidth approximation for trees

Anupam Gupta

Research output: Contribution to conferencePaperpeer-review


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 languageEnglish (US)
Number of pages6
StatePublished - 2000
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000


Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Improved bandwidth approximation for trees'. Together they form a unique fingerprint.

Cite this