TR97-017 Authors: Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

Publication: 9th May 1997 12:50

Downloads: 1937

Keywords:

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 [Pa76]. 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.