Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-APX-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V 8947 Approximation Algorithms for Bandwidth Problems on some large Graph Classes Juergen Wirtgen [Download PostScript] [Download PDF] The {\em 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 {\em minimal}. The {\em 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 {\em minimal}, over all numberings and images. Both problems have a long history and they are known to be $NP$-hard \cite{Pap76}, \cite{MaPaSu85}. In this paper we present the first $PTAS$ for the topological bandwidth of trees. Furthermore we construct $n^{\epsilon}$-approximation algorithms for the bandwidth of graphs with minimum degree $n^{\delta}$, for any $\delta, \epsilon >0$. Last Change: 11/05/14 at 10:11:54  English Universität Bonn -> Institut für Informatik -> Abteilung V