MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Partitioning techniques for the Steiner problem

Polzin, Tobias and Vahdati, Siavash

December 2001, 21 pages.

Status: available - back from printing

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.

  • Attachement: (397 KBytes); 2001-1-006.pdf (12850 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Polzin, Tobias and Vahdati, Siavash},
  TITLE = {Partitioning techniques for the Steiner problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2001-1-006},
  MONTH = {December},
  YEAR = {2001},
  ISSN = {0946-011X},