Improved Steiner tree approximation in graphs

By Gabriel Robins, A. Zelikovsky. ACM-SIAM Symposium on Discrete Algorithms, 2000

625 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/3671736e7a39e7855c33154e6fa76b2a256e8bc7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Steven S. Skiena
2. Errol L. Lloyd
3. Rui Liu
4. Madhav V. Marathe
5. Ram Ramanathan
6. S. Ravi
7. Gabriel Robins
8. A. Zelikovsky

Citations in the corpus

• Tighter Bounds for Graph Steiner Tree Approximation (2005, background): “A preliminary version of this work appeared in [20].”
• Network coding for large scale content distribution (2005, background): “RELATED WORK Implementing large scale content distribution using endsystem cooperation techniques has been the focus of multiple research efforts during the recent years.”
• Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks (2002, methodology): “An approximation algorithm with a performance guarantee of (1+ln √ 3 ) is known for the Steiner tree problem in graphs [ 25 ].”
• The Algorithm Design Manual (2020, methodology): “55-factor approximation for Steiner trees on graphs is due to Robins and Zelikovsky [RZ05].”