Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1998 Copyright 1998 University of Bonn, Department of Computer Science, Abt. V
85189

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V