MPI-I-2001-1-006
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.
-
2001-1-006.pdf
- Attachement: partition.ps.gz (397 KBytes); 2001-1-006.pdf (12850 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2001-1-006
BibTeX
@TECHREPORT{PolzinVahdati2001b,
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},
}