A polynomial-time approximation scheme for Steiner tree in planar graphs

ABSTRACT

We give an O(n log n) approximation scheme for Steiner tree in planar graphs.

REFERENCES

• 1: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 2: Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , Andrzej Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.33-41, January 25-27, 1998, San Francisco, California, United States
• 3: Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650]
• 4: M. Bern. Faster exact algorithms for steiner trees in planar networks. Networks, 20:109--120, 1990.
• 5: M. Bern and D. Bienstock. Polynomially solvable special cases of the steiner problem in planar networks. Annals of Operations Research, 33:405--418, 1991.
• 6: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
• 7: Ranel E. Erickson , Clyde L. Monma , Arthur F. Veinott, Jr., Send-and-split method for minimum-concave-cost network flows, Mathematics of Operations Research, v.12 n.4, p.634-664, Nov. 1987 [doi>10.1287/moor.12.4.634]
• 8: I. Hicks, A. Koster, and E. Kolotoǧlu. Branch and tree decomposition techniques for discrete optimization. In J. Smith, editor, TutORials 2005, INFORMS TutORials in Operations Research Series, chapter 1, pages 1-29. INFORMS Annual Meeting, 2005.
• 9: Philip N. Klein, A linear-time approximation scheme for planar weighted TSP, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.647-657, October 23-25, 2005 [doi>10.1109/SFCS.2005.7]
• 10: Philip N. Klein, A subset spanner for Planar graphs,: with application to subset TSP, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132620]
• 11: L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Informatica, 15:141--145, 1981.
• 12: Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X]
• 13: J. Scott Provan, An approximation scheme for finding Steiner trees with obstacles, SIAM Journal on Computing, v.17 n.5, p.920-934, October 1988 [doi>10.1137/0217057]
• 14: J. S. Provan, Convexity and the Steiner tree problem, Networks, v.18 n.1, p.55-72, Spring 1988 [doi>10.1002/net.3230180108]
• 15: Satish B. Rao , Warren D. Smith, Approximating geometrical graphs via “spanners” and “banyans”, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.540-550, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276868]
• 16: H. Takahashi and A. Matsuyama. An approximate solution for the steiner problem in graphs. Mathematica Japonicae, 24:571--577, 1980.
• 17: P Widmayer, On approximation algorithms for Steiner's problem in graphs, International Workshop WG '86 on Graph-theoretic concepts in computer science, p.17-28, June 1987, Bernried, Germany
• 18: Y F Wu , P Widmayer , C K Wong, A faster approximation algorithm for the Steiner problem in graphs, Acta Informatica, v.23 n.2, p.223-229, April 1986 [doi>10.1007/BF00289500]