Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem

2007; Elsevier BV; Volume: 103; Issue: 5 Linguagem: Inglês

10.1016/j.ipl.2007.03.012

1872-6119

Paulo Feofiloff, Cristina G. Fernandes, Carlos Eduardo Ferreira, José Coelho de Pina,

Advanced Graph Theory Research

The primal-dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2-1/(n-1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n^3logn) time-it applies the primal-dual scheme once for each of the n vertices of the graph. We present a primal-dual algorithm that runs in O(n^2logn), as it applies this scheme only once, and achieves the slightly better ratio of (2-2/n). We also show a tight example for the analysis of the algorithm and discuss briefly a couple of other algorithms described in the literature.