Steiner trees with n terminals among n + 1 nodes

Let G=(V,E) be connected undirected graph and N a subset of distinguished nodes, called terminals. A Steiner tree on [G,N] is a minimal tree connecting all the terminal nodes. Restricting the instances to the case /N/=/N/-1, we present an algorithm to construct a minimum weight Steiner tree for any weight function on the edges E of G, and a complete minimal description of the polytope defined as the convex hull of all steiner trees on [G,N].


Published in:
Operations Research Letters, 11, 125-133
Year:
1992
Note:
PRO 92.07
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)