Groupe d’études et de recherche en analyse des décisions

# Steiner trees with edge capacities

## Cédric Bentz – CNAM-CEDRIC, France

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 such that, 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.

Entrée gratuite.
Bienvenue à tous.