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.