Solving group Steiner problems as Steiner problems

Solving group Steiner problems as Steiner problems

0.00 Avg rating0 Votes
Article ID: iaor20051911
Country: Netherlands
Volume: 154
Issue: 1
Start Page Number: 323
End Page Number: 329
Publication Date: Apr 2004
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics, networks
Abstract:

The generalized spanning tree or group Steiner problem (GSP) is a generalization of the Steiner problem in graphs (SPG): one requires a tree spanning (at least) one vertex of each subset, given in a family of vertex subsets, while minimizing the sum of the corresponding edge costs. Specialized solution procedures have been developed for this problem. In this paper we investigate the performance of a known but so far neglected transformation to the undirected Steiner problem in graphs. When combined with a recent metaheuristic for the SPG this straightforward approach compares favorably with specialized GSP heuristics. Thus we set a standard for future algorithms.

Reviews

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