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.