## Seminar: Computing Optimal Steiner Trees in Graphs |

## Sommer-Semester 2016 |

This seminar deals with methods to compute optimal Steiner trees in graphs and variants thereof. We will review the methods and results of the 11th DIMACS Implementation Challenge: Steiner Tree Problems. Broadly speaking, the goal of a Steiner tree problem is to find an optimal way (with respect to a specified criterion) of connecting a given set of objects. In most common variants, these objects are either points in a metric space or a subset of the vertices of a network. Most of these problems are NP-hard, with the decision variant of the classic Steiner tree problem in graphs being one of Karp's famous 21 NP-complete problems, and real-world applications can be found for instance in the design of large-scale computer circuits, multicast routing in communication networks, network optimization, computer-aided design and phylogenetic tree reconstruction.

Wednesday, April 20, 2016 at 10:00 h ct in room MA 651 at TU.

The kickoff, where every participant will give an overview (of at most five minutes) on their topic, will take place on

Friday, May 13, 2016 at 10:00 h ct in room H 3012 at TU.

Finally, the main talks will be held on

and onJune 30th at 11:15 at ZIB, lecture hall

Dates and rooms are subject to change. Further dates will be appointed if neccessary.

1. RS - A Robust and Scalable Algorithm for the Steiner Problem in Graphs (Thomas Pajor, Eduardo Uchoa and Renato Werneck)Classical Steiner Problem in Graphs

2. PN - Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks (Krzysztof Ciebiera, Piotr Sankowski, Piotr Godlewski and Piotr Wygocki)

3. TN - Dijkstra meets Steiner: Computational results of a fast exact Steiner tree algorithm (Stefan Hougardy, Jannik Silvanus and Jens Vygen)

4. FW - The GeoSteiner Software Package for Computing Steiner Trees in the Plane: An Updated Computational Study (Daniel Juhl, David M. Warme, Pawel Winter and Martin Zachari- asen)Euclidean and Rectilinear Steiner Problem

5. TMN - Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces (Rasmus Fonseca, Marcus Brazil, Pawel Winter and Martin Zachariasen)

6. AR - Solving the Maximum-Weight Connected Subgraph Problem to Optimality (Mohammed El-Kebir and Gunnar W. Klau)Prize-Collecting Variants

7. MS- Algorithms for the Maximum Weight Connected Subgraph and Prize- collecting Steiner Tree Problems (Ernst Althaus and Markus Blumenstock)

8. LE - A Fast, Adaptive Variant of the Goemans-Williamson Scheme for the Prize-Collecting Steiner Tree Problem (Chinmay Hegde, Piotr Indyk and Ludwig Schmidt)

9. JH - Local Search Heuristics for Hop-constrained Directed Steiner Tree Problem (Oleg Burdakov, Jonas Kvarnstrom and Patrick Doherty)Further Variants

10. RR - Generalized local branching heuristics and the capacitated ring tree problem (Alessandro Hill and Stefan Voss)

11. MSE - A Heuristic Approach for the Stochastic Steiner Tree Problem (Pedro Hokama et al)

A list of possible seminar papers can be found here.