ALCOMFT-TR-02-38

Tobias Polzin and Siavash Vahdati Daneshmand
Partitioning Techniques for the Steiner Problem
MPI. Work packages 2 and 5. May 2002.

Abstract: Partitioning is one of the basic ideas for designing efficient algorithms, but on \NP-hard problems like the Steiner problem, straightforward application of the classical paradigms for exploiting this idea rarely leads to empirically successful algorithms. In this paper, we present a new approach that is based on vertex separators. We show several contexts in which this approach can be used profitably. Our approach is new in the sense that it uses partitioning to design reduction methods. We introduce two such methods and show their impact empirically. These methods are integrated into a program package, which presently achieves by far the best results on a wide range of benchmark instances of the Steiner problem in networks.

Postscript file: ALCOMFT-TR-02-38.ps.gz (474 kb).