Publication Details
Title: An Approximation Algorithm for the Bandwidth Problem on Dense Graphs
Author: M. Karpinski, J. Wirtgen, and A. Zelikovsky
Group: ICSI Technical Reports
Date: May 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-016.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-97-016
Bibliographic Reference:
M. Karpinski, J. Wirtgen, and A. Zelikovsky. An Approximation Algorithm for the Bandwidth Problem on Dense Graphs. ICSI Technical Report TR-97-016, May 1997
Author: M. Karpinski, J. Wirtgen, and A. Zelikovsky
Group: ICSI Technical Reports
Date: May 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-016.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-97-016
Bibliographic Reference:
M. Karpinski, J. Wirtgen, and A. Zelikovsky. An Approximation Algorithm for the Bandwidth Problem on Dense Graphs. ICSI Technical Report TR-97-016, May 1997