A Generic Approach to Solving the Steiner Tree Problem and Variants

Please always quote using this URN: urn:nbn:de:0297-zib-57817
  • Spawned by practical applications, numerous variations of the classical Steiner tree problem in graphs have been studied during the last decades. Despite the strong relationship between the different variants, solution approaches employed so far have been prevalently problem-specific. In contrast, we pursue a general-purpose strategy resulting in a solver able to solve both the classical Steiner tree problem and ten of its variants without modification. These variants include well-known problems such as the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem or the rectilinear minimum Steiner tree problem. Bolstered by a variety of new methods, most notably reduction techniques, our solver is not only of unprecedented versatility, but furthermore competitive or even superior to specialized state-of-the-art programs for several Steiner problem variants.

Export metadata

  • Export Bibtex
Author:Daniel Rehfeldt
Document Type:Master's Thesis
Tag:Steiner Tree Problem; Steiner Tree Problem Variants
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx)
CCS-Classification:D. Software
Granting Institution:Technische Universit├Ąt Berlin
Advisor:Thorsten Koch
Date of final exam:2015/09/11
Year of first publication:2015

$Rev: 13581 $