Institut für Informatik
 
Abteilung V

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

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 NP-complete \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