In [8], Petingi and Rodriguez prove that if $''G$ '' is $''k$''-edge-connected in $''T$ '' and $<math>\vert T\vert\geq 2$</math>, then $''G$ '' contains at least $<math>\lfloor (\frac{2}{3})^{\vert V-T\vert}k/2 \rfloor$ </math> edge-disjoint Steiner trees for $''T$''.
Comment Matthias Kriesell [4] proved that if ''G'' is <math>(012k + 2\vert V-T\vert)</math>-edge-connected in ''T'' then ''G'' contains at least ''k'' edge-disjoint Steiner trees for ''T''.03This result is stronger than the above cited result in [8].2004)
Matthias Kriesell Lap Chi Lau [45] has proved that if $''G$ '' is $(2k + 2\vert V-T\vert)$''26k''-edge-connected in $T$ then $G$ contains at least $it has ''k$ '' edge-disjoint Steiner trees for $T$. This result is stronger than gives the above cited first constant factor approximation result in [8]for the edge-disjoint Steiner trees problem.
Comment (Joseph Cheriyan and Mohammad R. Salavatipour, 19[1] proved that the problem of finding maximum number of edge-disjoint (or vertex-disjoint) Steiner trees is APX-hard even if there are only 4 terminals.08.2004They also showed that the directed version is hard to approximate within factor of <math>O(n^{\frac{1}{3}-\epsilon})</math> for any <math>\epsilon>0</math>, and gave an algorithm with approximation guarantee of <math>O(n^{\frac{1}{2}+\epsilon})</math>.
Lap Chi Lau [5] has proved that if $G$ is $26k$-edge-connected then it has $k$ edge-disjoint Steiner trees. This gives the first constant factor approximation result for the edge-disjoint Steiner trees problem.
Joseph Cheriyan and Mohammad R. Salavatipour [1] proved that the problem of finding maximum number of edge-disjoint (or vertex-disjoint) Steiner trees is APX-hard even if there are only 4 terminals. They also showed that the directed version is hard to approximate within factor of $O(n^{\frac{1}{3}-\epsilon})$ for any $\epsilon>0$, and gave an algorithm with approximation guarantee of $O(n^{\frac{1}{2}+\epsilon})$.
Bibliography
1
