Approximation Algorithms for Bandwidth Problems on some large Graph Classes
J urgen Wirtgen · 1998
The bandwidth problem is the problem of numbering the vertices of a given graph G so that the maximum difference between the numbers of adjacent vertices is minimal. The topological bandwidth problem is a natural extension of the bandwidth problem. It is the problem of numbering the vertices of a homeomorphic image of a given graph G so that the maximum difference between the numbers of adjacent vertices is minimal, over all numberings and images. Both problems have a long history and they are known to be NP-hard [Pa 76], [MPS 85]. In this paper we present the first PTAS for the topological bandwidth of trees. Furthermore we construct n ffl -approximation algorithms for the bandwidth of graphs with minimum degree n ffi , for any ffi; ffl ? 0. Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by the ESPRIT BR Grants 7097 and EC-US 030. Email: [email protected] 1 Introduction Graph layout problems are a collection of simple graph problems...