An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

TitleAn Approximation Algorithm for the Bandwidth Problem on Dense Graphs
Publication TypeTechnical Report
Year of Publication1997
AuthorsKarpinski, M., Wirtgen J., & Zelikovsky A.
Other Numbers1083
Abstract

The bandwidth problem is the problem of numbering the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and is known to be NP-complete [Papadimitriou, 1997]. Only few special cases of this problem are known to be efficiently approximable. In this paper we present the first constant approximation ratio algorithms on dense instances of this problem.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1997/tr-97-016.pdf
Bibliographic Notes

ICSI Technical Report TR-97-016

Abbreviated Authors

M. Karpinski, J. Wirtgen, and A. Zelikovsky

ICSI Publication Type

Technical Report