Item

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 which 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.