How Many Steiner Terminals Can You Connect in 20 Years?

Please always quote using this URN: urn:nbn:de:0297-zib-42524
  • Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.

Download full text files

Export metadata

Metadaten
Author:Ralf Borndörfer, Nam-Dung Hoang, Marika Karbstein, Thorsten Koch, Alexander Martin
Document Type:ZIB-Report
Tag:Steiner connectivity; Steiner tree; Steiner tree packing
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
Date of first Publication:2013/09/20
Series (Serial Number):ZIB-Report (13-57)
ISSN:1438-0064
Published in:Appeared in: Facets of Combinatorial Optimization Festschrift for Martin Grötschel. Jünger, Michael; Reinelt, Gerhard (Eds.) Springer 2013, pp. 215-244
DOI:https://doi.org/10.1007/978-3-642-38189-8_10