Steiner tree problems with profits

Abstract

This is a survey of the Steiner tree problem with profits, a variation of the classical Steiner problem where, besides the costs associated with edges, there are also revenues associated with vertices. The relationships between these costs and revenues are taken into consideration when deciding which vertices should be spanned by the solution tree. The survey contains a classification of the problems falling within this category and an overview of the methods developed to solve them. It also lists several graph preprocessing procedures and analyzes their validity for the different variants of the problem. Finally, a brief comparison is made between the profit versions of the Steiner tree pro..