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].
- View record in Web of Science
Record created on 2006-02-13, modified on 2016-08-08