ALCOMFT-TR-02-135

Tobias Polzin and Siavash Vahdati Daneshmand
Extending Reduction Techniques for the Steiner Tree Problem
MPI. Work packages 2 and 5. June 2002.

Abstract: Reduction methods are a key ingredient of the most successful algorithms for the Steiner problem. Whereas classical reduction tests just considered single vertices or edges, recent and more sophisticated tests extend the scope of inspection to more general patterns. In this paper, we present such an extended reduction test, which generalizes different 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 contributions. The experimental results show a large improvement over previous methods using the idea of extension, leading to a drastic speed-up in the optimal solution process and the solution of several previously unsolved benchmark instances.

Postscript file: ALCOMFT-TR-02-135.ps.gz (104 kb).