Lecture Notes in Computer Science, 2002, Volume 2461/2002, 795-807, DOI: 10.1007/3-540-45749-6_69

Extending Reduction Techniques for the Steiner Tree Problem

Tobias Polzin and Siavash Vahdati Daneshmand

View Related Documents

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.

Keywords  Steiner Problem - Reductions

Fulltext Preview

Image of the first page of the fulltext document