Algorithms for the Steiner Problem in networks
Tobias Polzin · 2003
The Steiner problem in networks is the problem of connecting a set of required vertices in a weighted graph at minimum cost. It is a classical N P-hard problem with many important applications. For this problem we develop, implement and test several new techniques. On the side of lower bounds, we present a hierarchy of linear relaxations and class of new relaxations that are the currently strongest polynomially solvable linear relaxations. On the side of preprocessing techniques, we improve some known reduction tests and introduce powerful new ones. For upper bounds we introduce the successful concept of heuristic reductions. Finally, we integrate these blocks into an exact algorithm. For the exact algorithm and for the different components we present very good computational results on the large benchmark library SteinLib.