A Steiner tree problem with capacity constraints

Cédric Bentz, Marie-Christine Costa and Alain Hertz
july, 2014
Type de publication :
Conférence sans actes
Conférence :
GO IX, Ninth international colloquium on Graphs and Optimization, 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...
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},
}