MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


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

Polzin, Tobias and Vahdati, Siavash

2002, 9 pages.

Status: available - back from printing

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.

  • Attachement: (3141 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  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},