[BCH14a] A Steiner tree problem with capacity constraints

Conférence Internationale avec comité de lecture : GO IX, Ninth international colloquium on Graphs and Optimization, July 2014, pp.12, Sirmione, Italy,

Mots clés: Steiner tree, graph, complexity, algorithm

Résumé: Given a weighted graph G with n nodes and a unique root r, the Steiner arborescence problem is to find a minimum cost arborescence T rooted at r and spanning a specified set of nodes called terminals. We introduce capacity constraints: at each node v there is a given upper bound of the number of terminals belonging to the sub-tree of T rooted at v. We will show that such problems appear in the design of wind farm collection networks. We also consider the associated Steiner flow problem where we have to route one unit of flow from r to each terminal. We give some complexity results or algorithms for different cases: for undirected graphs, for directed graphs with or without circuits, with or without costs on the edges, with a given number of terminals...

Equipe: oc


@inproceedings {
title="{A Steiner tree problem with capacity constraints}",
author=" C. Bentz and M.-C. Costa and A. Hertz ",
booktitle="{GO IX, Ninth international colloquium on Graphs and Optimization}",
address="Sirmione, Italy",