Extending reduction techniques for the Steiner tree problem: a combination of alternative-and bound-based approaches
Tobias Polzin, Siavash Vahdati · Max Planck Digital Library · 2001
A key ingredient of the most successful algorithms for the Steiner problem are reduction methods, i.e. methods to reduce the size of a given instance while preserving at least one optimal solution (or the ability to eciently reconstruct one). While classical reduction tests just inspected simple patterns (vertices or edges), recent and more sophisticated tests extend the scope of inspection to more general patterns (like trees). In this paper, we present such an extended reduction test, which generalizes dierent tests in the literature. We use the new approach of combining alternative- and bound-based methods, which substantially improves the impact of the tests. We also present several algorithmic improvements, especially for the computation of the needed information. The experimental results show a substantial improvement over previous methods using the idea of extension.