Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 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 k-Steiner Tree Problem, the ε-Dense Prize Collecting Steiner Tree Problem, the ε-Dense k-Steiner 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