Exact algorithms for the Steiner tree problem

Xinhui Wang

Research output: ThesisPhD Thesis - Research UT, graduation UT

308 Downloads (Pure)

Abstract

The Steiner tree problem is one of the original 21 NP complete problems, which has wide application in theorey and industry. There are no polynomial time algorithms for it, and exact (acceptable exponential time) algorithms are the best we can obtain for pursuing the exact solution for the all these problems. The main issue in exact algorithms is to improve the worst case bounds, which is very interesting from both theoretical and practical point of view. In this thesis, I have presented some of our contributions on this problem. In the first chapter, we have introduced some backgrounds of the Steiner tree problem. For easy understanding, we have explained some facts about complexity theory, especially the definition of NP has been introduced. Some recent results about algorithms for the Steiner tree problem are also summarized. In Chapter 2, some properties about rectilinear Steiner trees have been presented, since the second part of our main contribution concerned with this problem. Every rectilinear Steiner tree problem admits an optimal tree $T^*$ which is composed of tree stars. Moreover, the currently fastest algorithms for the rectilinear Steiner tree problem proceed by composing an optimum tree $T^*$ from tree star components in the cheapest way. The efficiency of such algorithms depends heavily on the number of tree stars (candidate components). Several empty region conditions are introduced for tree stars. In addition, the well know two-phase algorithm is explained for the rectilinear Steiner tree problem. First part of our work is two novel exact algorithms for the Steiner tree problem, which we present in Chapter 3. The well known algorithm for the Steiner tree problem is a dynamic programming algorithm, which was found by Dreyfus and Wagner. The complexity of this algorithm is $O^*(3^k),$ where $k$ is the number of terminal points. In this chapter, we first present a new algorithm in time $O^*(2.684^k)$ by showing that the optimum Steiner tree T can be partitioned into $T = T1 \cup T2 \cup T3$ and each $T_i$ is a minimum Steiner tree in a contracted graph $G_i$ with less than $0.4361k$ terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in $O^*(2.386^k).$ In this case, our splitting technique yields an improvement to $O^*(2.335^k)$ with $|G_i| \leq 0.477k$ Another algorithm is in time of $O^*((2+\delta)^k)$ for any $\delta > 0.$ Since the optimal tree can be separated into (many) components of size at most $\epsilon k + 1,$ the optimal tree for all the small components will be generated first in our algorithm. Thus, the optimal tree is achieved by adding such components (in some order), one at a time, until the constructed tree span all terminals. The other part of our contribution is about the number of tree star. Fössmeier and Kaufmann showed that any problem instance with $k$ terminals had a number of tree stars in between $1.32^k$ and $1.38^k$ in the worst case. A new forbidden case for tree star is achieved by us, which is followed by an exact bound of the tree star $O^*(\rho^k)$ where $\rho \approx 1.357.$ Two new forbidden cases are derived later for the candidate components. According to these forbidden cases, the upper bound $O^*(1.337^k)$ is obtained for the number of candidate components. Finally, a necessary condition, so called “two layer condition��? is presented for the tree star to be candidate component. Moreover, an optimal topological structure for the optimal tree in the “decreasing case��? is achieved from the “two layer condition��?.
Original languageUndefined
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

Cite this