Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 1997 Copyright 1997 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V