ECCC-Report TR97-017https://eccc.weizmann.ac.il/report/1997/017Comments and Revisions published for TR97-017en-usFri, 09 May 1997 12:50:17 +0300
Paper TR97-017
| An Approximation Algorithm for the Bandwidth Problem on Dense Graphs |
Marek Karpinski,
Juergen Wirtgen,
Alexander Zelikovsky
https://eccc.weizmann.ac.il/report/1997/017The 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.
Fri, 09 May 1997 12:50:17 +0300https://eccc.weizmann.ac.il/report/1997/017