
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1997  Copyright 1997 Universität Bonn, Institut für Informatik, Abt. V  
85176

NPHardness of the Bandwidth Problem on Dense Graphs
Marek Karpinski, Juergen Wirtgen [Download PostScript] [Download PDF] The {\em 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 {\em minimal}. The problem has a long and varied history and is known to be $NP$hard Papadimitriou \cite{Pap76}. Recently for dense graphs a constant ratio approximation algorithm for this problem has been constructed in Karpinski, Wirtgen and Zelikovsky \cite{KaWiZe97}. In this paper we prove that the bandwidth problem on the dense instances remains $NP$hard. 

Last Change:
08/18/99 at 13:00:38
English 
Universität Bonn > Institut für Informatik > Abteilung V 