Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Solving Steiner Tree Problems in Graphs to Optimality

Please always quote using this URN: urn:nbn:de:0297-zib-2526
  • 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 all problem instances discussed in literature to optimality, including one to our knowledge not yet solved problem. 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 {\em SteinLib} that is accessible via World Wide Web.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Thorsten KochORCiD, Alexander Martin
Document Type:ZIB-Report
Date of first Publication:1996/11/27
Series (Serial Number):ZIB-Report (SC-96-42)
ZIB-Reportnumber:SC-96-42
Published in:Appeared in: Networks 32, 1998, 207-232
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.