Exact algorithms for the Steiner tree problem

Xinhui Wang

Research output: ThesisPhD Thesis - Research UT, graduation UT

886 Downloads (Pure)

Abstract

In this thesis, the exact algorithms for the Steiner tree problem have been investigated. The Dreyfus-Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O(3k), where k is the number of the terminals.Firstly, two exact algorithms for the Steiner tree problem will be presented. The first one improves the running time of algorithm to O(2.684k) by showing that the optimum Steiner tree T can be partitioned into T = T1 [ T2 [ T3 in a certain way such that each Ti is a minimum Steiner tree in a suitable contracted graph Gi with less than k/2 terminals. The second algorithm is in time O((2 + )k) for any > 0. Every rectilinear Steiner tree problem admits an optimal tree T which is composed of tree stars. Moreover, the currently fastest algorithm for the rectilinear Steiner tree problem proceeds by composing an optimum tree T from tree star components in the cheapest way. F¨oßmeier and Kaufmann showed that any problem instance with k terminals has a number of tree stars in between 1.32k and 1.38k. We also present additional conditions on tree stars which allow us to further reduce the number of candidate components building the optimum Steiner tree to O(1.337k).
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Woeginger, Gerhard, Supervisor
  • Kern, Walter , Advisor
Thesis sponsors
Award date25 Jun 2008
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-2660-9
DOIs
Publication statusPublished - 25 Jun 2008

Keywords

  • EWI-13611
  • METIS-252055
  • IR-59035

Fingerprint

Dive into the research topics of 'Exact algorithms for the Steiner tree problem'. Together they form a unique fingerprint.

Cite this