Optimization Online


Steiner Trees with Degree Constraints: Structural Results and an Exact Solution Approach

Frauke Liers(frauke.liers***at***math.uni-erlangen.de)
Alexander Martin(alexander.martin***at***math.uni-erlangen.de)
Susanne Pape(susanne.pape***at***math.uni-erlangen.de)

Abstract: In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we first focus on binary Steiner trees in which all node degrees are required to be at most three. We then present results for general degree-constrained Steiner trees. It is shown that finding a binary Steiner is NP-complete for arbitrary graphs. We relate the problem to Steiner trees without degree constraints as well as degree-constrained spanning trees by proving approximation ratios. Further, we give some integer programming formulation for this problem on undirected and directed graphs and study the associated polytope for both cases. Some classes of facets are introduced. Based on this study a branch-&-cut approach is developed and evaluated on biological instances coming from the reconstruction of phylogenetic trees. We are able to solve nearly all instances up to 200 nodes to optimality within a limited amount of time. This shows the effectiveness of our approach.

Keywords: Steiner tree, degree constraint, Steiner ratio, integer programming, polytope, branch-&-cut

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: November 2014

Download: [PDF]

Entry Submitted: 12/05/2014
Entry Accepted: 01/03/2015
Entry Last Modified: 12/05/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society