Abstract

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].

Details

Actions