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