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