Networks · 1998 · 250 citations · 29 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationBranch And BoundCombinatorial OptimizationDiscrete OptimizationGraph AlgorithmsGraph TheoryInteger ProgrammingAlgorithmic Graph TheoryBranch-and-cutCircuit Graph TheoryGraph OptimizationHeuristicsNetwork Design ProblemsSteiner Tree ProblemTree Algorithms
The paper implements a branch‑and‑cut algorithm to solve Steiner tree problems in graphs. The algorithm uses an integer programming formulation for directed graphs, with preprocessing, separation, and primal heuristics, and the test instances are provided in the SteinLib library online. The algorithm solves almost all benchmark instances to optimality, including a previously unsolved case, and demonstrates scalability on large electronic‑circuit Steiner tree problems. © 1998 John Wiley & Sons, Inc., Networks 32:207–232.
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. © 1998 John Wiley & Sons, Inc. Networks 32: 207–232, 1998
29
An approximate solution for the Steiner problem in graphs
Haruhisa Takahashi, A Matsuyama · Mathematica japonica · 1980 · 884 citations
Stuart E. Dreyfus, Robert A. Wagner · Networks · 1971 · 693 citations
F. K. Hwang, Dana Richards · Networks · 1992 · 664 citations