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

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs
Marek Karpinski, Juergen Wirtgen, Alex Zelikovsky [Download PostScript] [Download PDF] The bandwidth problem is the problem of numbering the vertices of a given graph $G$ such that the maximum difference between two numbers of adjacent vertices is minimal. The problem is known to be NPcomplete \cite{Pap76} and there are only few algorithms for rather special cases of the problem \cite{HaMaMo91} \cite{Kra87} \cite{Sax80} \cite{Smi95}. In this paper we present a randomized $3$approximation algorithm for the bandwidth problem restricted to dense graphs and a randomized $2$approximation algorithm for the same problem on directed dense graphs. 

Last Change:
11/05/14 at 10:07:37
English 
Universität Bonn > Institut für Informatik > Abteilung V 