An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

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 [Pa 76] and there are only few algorithms for rather special cases of the problem [HMM 91] [Kr 87] [Sa 80] [Sm 95]. In this paper we present a randomized 3approximation algorithm for the bandwidth problem restricted to dense graphs and a randomized 2-approximation algorithm for the same problem on directed dense graphs. x Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by DFG Grant KA 673/4-1, by the ESPRIT BR Grants 7097 and EC-US 030. Email: marek@cs.bonn.edu. -- Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by the ESPRIT BR Grants 7097 and EC-US 030. Email: wirtgen@cs.bonn.edu k Dept. of Computer Science, University of Bonn, 53117 Bonn. Visiting from Dept. of Computer Science, Thornton Hall, U...