Reduction Tests for the Prize-Collecting Steiner Problem

Published: 2004/08/31, Updated: 2005/03/14

Applications - OR and Management Sciences, Integer Programming, Telecommunications preprocessing, reduction tests, steiner problem Short URL: https://optimization-online.org/?p=8965

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.

Reduction Tests for the Prize-Collecting Steiner Problem

Citation

Article