Reduction Tests for the Prize-Collecting Steiner Problem

Eduardo Uchoa (uchoaproducao.uff.br)

Abstract: 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.

Keywords: Steiner problem, Preprocessing, reduction tests

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Integer Programming

Citation: Operations Research Letters, to appear.

Download: [PDF]

Entry Submitted: 08/31/2004
Entry Accepted: 09/01/2004
Entry Last Modified: 03/14/2005

Modify/Update this entry