Premium
A catalog of steiner tree formulations
Author(s) -
Goemans Michel X.,
Myung YoungSoo
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230104
Subject(s) - steiner tree problem , combinatorics , equivalence (formal languages) , vertex (graph theory) , mathematics , relaxation (psychology) , tree (set theory) , discrete mathematics , computer science , graph , psychology , social psychology
We present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxations. The motivation behind this study is a characterization of the feasible region of the dicut relaxation in the natural space corresponding to the Steiner tree problem. © 1993 by John Wiley & Sons, Inc.