Steiner tree problems with profits

Steiner tree problems with profits

0.00 Avg rating0 Votes
Article ID: iaor20073393
Country: Canada
Volume: 44
Issue: 2
Start Page Number: 99
End Page Number: 116
Publication Date: May 2006
Journal: INFOR
Authors: , ,
Keywords: programming: travelling salesman
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 problem and of the travelling salesman problem.

Reviews

Required fields are marked *. Your email address will not be published.