MPI-I-2002-1-001

Using (sub)graphs of small width for solving the Steiner problem

Polzin, Tobias and Vahdati, Siavash

MPI-I-2002-1-001. 2002, 9 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
For the Steiner tree problem in networks, we present a practical algorithm
that uses the fixed-parameter tractability of
the problem with respect to a certain width parameter closely
related to pathwidth. The running time of the algorithm is linear in
the number of vertices when the pathwidth is constant. Combining this
algorithm with our previous techniques, we can already profit from
small width in subgraphs of an instance. Integrating this
algorithm into our program package for the Steiner problem
accelerates the solution process on some groups of instances and
leads to a fast solution of
some previously unsolved benchmark instances.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	3141 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2002-1-001

BibTeX
@TECHREPORT{PolzinVahdati2002, AUTHOR = {Polzin, Tobias and Vahdati, Siavash}, TITLE = {Using (sub)graphs of small width for solving 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-2002-1-001}, YEAR = {2002}, ISSN = {0946-011X},}