Solving group Steiner problems as Steiner tree problems

Link:
Autor/in:
Erscheinungsjahr:
2004
Medientyp:
Text
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/06db8436-9cbc-459d-8704-7faad21870f7