15.02.2008

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.