Journal article

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


  • There is no available fulltext. Please contact the lab or the authors.

Related material