A Steiner tree problem with capacity constraints
july, 2014
Publication type:
Conference without proceedings
Conference:
GO IX, Ninth international colloquium on Graphs and Optimization, Sirmione, Italy,
Keywords :
Steiner tree, graph, complexity, algorithm
Abstract:
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...
BibTeX:
@conference{Ben-Cos-Her-2014, author={Cédric Bentz and Marie-Christine Costa and Alain Hertz }, title={A Steiner tree problem with capacity constraints }, publisher={GO IX, Ninth international colloquium on Graphs and Optimization, Sirmione, Italy, }, year={2014 }, month={7}, }