
University of Bonn > Department of Computer Science > Chair V  
CSReports 2008  Copyright 2008 University of Bonn, Department of Computer Science, Abt. V  
85287 15.02.2008 
On the Approximability of Dense Steiner Problems
Mathias Hauptmann [Download PostScript] [Download PDF] The εDense Steiner Tree Problem was defined by Karpinski and Zelikovsky (1997) who proved that for each ε>0, this problem admits a PTAS. Based on their method we consider here dense versions of various Steiner Tree problems. In particular, we give polynomial time approximation schemes for the εDense kSteiner Tree Problem, the εDense Prize Collecting Steiner Tree Problem, the εDense kSteiner Tree Problem and the εDense Group Steiner Tree Problem. For the dense version of the Steiner Forest Problem we obtain an approximation algorithm that performs well if the number of terminal sets is small compared to the total number of terminals. 

Last Change:
11/05/14 at 10:42:03
Deutsch 
University of Bonn > Department of Computer Science > Chair V 