Improved Bandwidth Approximation for Trees and Chordal Graphs

Anupam Gupta

Research output: Contribution to journalArticlepeer-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 difference between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known approximation algorithms for the minimum bandwidth linear arrangement (which are based on the principle of volume respecting embeddings) output a linear arrangement which has bandwidth within O(log3 n) of the optimal bandwidth. In this paper, we present a simple randomized O(log2.5 n)-approximation algorithm for bandwidth minimization on trees. We also show that a close variant of this algorithm gives a similar performance guarantee for chordal graphs.

Original languageEnglish (US)
Pages (from-to)24-36
Number of pages13
JournalJournal of Algorithms
Issue number1
StatePublished - Jul 2001

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Improved Bandwidth Approximation for Trees and Chordal Graphs'. Together they form a unique fingerprint.

Cite this