Loading...
research article
Steiner trees with n terminals among n + 1 nodes
Prodon, A.
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].
Type
research article
Web of Science ID
WOS:A1992JH84200001
Authors
Prodon, A.
Publication date
1992
Published in
Issue
11
Start page
125
End page
133
Note
PRO 92.07
Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
February 13, 2006
Use this identifier to reference this record