Title: Steiner trees with edge capacities

Speaker: Cédric Bentz – CNAM-CEDRIC, France

Abstract: Assume we are given a graph G=(V,E) (directed or not) with capacities and costs on the edges, a vertex r of G called root, and a set X of terminal vertices. The problem we consider is the following: find in G a minimum-cost tree rooted at r, spanning all the vertices in X, and suchthat, for each edge of this tree, the number of paths going from r to terminals and containing this edge does not exceed its capacity. When all capacities are at least |X|, then this is the classical Steiner tree problem, with a given root. The generalization we are interested in has several relevant applications, including the design of wind farm collection networks. We study the complexity of this problem in different settings: for instance, the graph may be directed or not, |X| may be fixed or not, the costs may be 0 or not. Whenever this is possible, we also design approximation algorithms to solve the problem.

Free entrance.
Welcome to everyone.