Binary Steiner Trees: Structural Results and an Exact Solution Approach

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autor(en): Liers F, Martin A, Pape S
Zeitschrift: Discrete Optimization
Verlag: Elsevier
Jahr der Veröffentlichung: 2016
Band: 21
Seitenbereich: 85-117
ISSN: 1572-5286
Sprache: Englisch


In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we focus on binary Steiner trees in which all node degrees are required to be at most three. It is shown that finding a binary Steiner tree 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 integer programming formulations for this problem on undirected and directed graphs and study the associated polytopes 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.

FAU-Autoren / FAU-Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Diskrete Optimierung in den Ingenieurwissenschaften
Martin, Alexander Prof. Dr.
Lehrstuhl für Wirtschaftsmathematik
Pape, Susanne
Lehrstuhl für Wirtschaftsmathematik

Zusätzliche Organisationseinheit(en)
Lehrstuhl für Wirtschaftsmathematik


Liers, F., Martin, A., & Pape, S. (2016). Binary Steiner Trees: Structural Results and an Exact Solution Approach. Discrete Optimization, 21, 85-117.

Liers, Frauke, Alexander Martin, and Susanne Pape. "Binary Steiner Trees: Structural Results and an Exact Solution Approach." Discrete Optimization 21 (2016): 85-117.


Zuletzt aktualisiert 2018-17-10 um 13:20