The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical applications on network design. This article introduces a proper redefinition of the concept of bottleneck Steiner distance on the PCSP context. This allows the application of known STP reduction tests on the PCSP in their full power.
Citation
Operations Research Letters, to appear.
Article
View Reduction Tests for the Prize-Collecting Steiner Problem