The prize-collecting generalized minimum spanning tree problem

The prize-collecting generalized minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor2009608
Country: Netherlands
Volume: 14
Issue: 1
Start Page Number: 69
End Page Number: 93
Publication Date: Feb 2008
Journal: Journal of Heuristics
Authors: , ,
Keywords: graphs
Abstract:

We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm.

Reviews

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