On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs

Indaco Biazzo, Alfredo Braunstein, Riccardo Zecchina

We study the behavior of an algorithm derived from the cavity method for the Prize-Collecting Steiner Tree (PCST) problem on graphs. The algorithm is based on the zero temperature…