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.
Entry Submitted: 08/31/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|