|
 
|
[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
BibTeX
| @inproceedings { | |||
| BCH14a, | |||
| 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}", | |
| year | = | 2014, | |
| month | = | "July", | |
| pages | = | "12", | |
| address | = | "Sirmione, Italy", | |
| } | |||
