Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V
8951

NP-Hardness of the Bandwidth Problem on Dense Graphs (Revised)
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 $\delta$-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: 11/05/14 at 10:10:18
 English
Universität Bonn -> Institut für Informatik -> Abteilung V