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: | Volgenant A., Duin C.W., Voss S. |
Keywords: | heuristics, networks |
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.