Solving Steiner Tree Problems in Graphs to Optimality

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autor(en): Koch T, Martin A
Zeitschrift: Networks
Verlag: Wiley-Blackwell
Jahr der Veröffentlichung: 1998
Band: 32
Seitenbereich: 207 -- 232
ISSN: 0028-3045
eISSN: 1097-0037
Sprache: Englisch


In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nearly all problem instances discussed in the literature to optimality, including one problem that - to our knowledge - has not yet been solved. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called SteinLib that is accessible via the World Wide Web.

FAU-Autoren / FAU-Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Wirtschaftsmathematik

Autor(en) der externen Einrichtung(en)
Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


Koch, T., & Martin, A. (1998). Solving Steiner Tree Problems in Graphs to Optimality. Networks, 32, 207 -- 232.

Koch, Thorsten, and Alexander Martin. "Solving Steiner Tree Problems in Graphs to Optimality." Networks 32 (1998): 207 -- 232.


Zuletzt aktualisiert 2018-08-08 um 03:04