An O(n log n) approximation scheme for Steiner tree in planar graphs

ABSTRACT

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O(n log n).

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: Piotr Berman , Viswanathan Ramaiyer, Improved approximations for the Steiner tree problem, Journal of Algorithms, v.17 n.3, p.381-408, Nov. 1994
• 5: Bern, M. 1990. Faster exact algorithms for Steiner trees in planar networks. Netw. 20, 109--120.
• 6: Bern, M., and Bienstock, D. 1991. Polynomially solvable special cases of the Steiner problem in planar networks. Math. Oper. Res. 33, 405--418.
• 7: 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]
• 8: Glencora Borradaile , Claire Kenyon-Mathieu , Philip Klein, A polynomial-time approximation scheme for Steiner tree in planar graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1285-1294, January 07-09, 2007, New Orleans, Louisiana
• 9: Glencora Borradaile , Philip Klein, The Two-Edge Connectivity Survivable Network Problem in Planar Graphs, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_40]
• 10: Borradaile, G., Klein, P., and Mathieu, C. 2007b. Steiner tree in planar graphs: An O(n log n) approximation scheme with singly exponential dependence on epsilon. In Proceedings of the 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 4619. Springer, 275--286.
• 11: Catalan, E. 1838. Note sur un problème de combinaisons. J. Mathématiques Pures et Appl. 3, 111 --112.
• 12: Erik D. Demaine , MohammadTaghi Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: 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]
• 14: Garey, M., and Johnson, D. S. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 4, 826--834.
• 15: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 16: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 17: Stefan Hougardy , Hans Jürgen Prömel, A 1.598 approximation algorithm for the Steiner problem in graphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.448-453, January 17-19, 1999, Baltimore, Maryland, United States
• 18: Karp, R. 1975. On the computational complexity of combinatorial problems. Netw. 5, 45--68.
• 19: Karpinski, M., and Zelikovsky, A. 1997. New approximation algorithms for the Steiner tree problem. J. Combin. Optimiz. 1, 47--65.
• 20: Klein, P. A linear-time approximation scheme for planar TSP. SIAM J. Comput. to appear.
• 21: 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]
• 22: 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]
• 23: Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 24: Kou, L., Markowsky, G., and Berman, L. 1981. A fast algorithm for Steiner trees. Acta Inf. 15, 141--145.
• 25: 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]
• 26: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 27: Hans Jürgen Prömel , Angelika Steger, RNC-Approximation Algorithms for the Steiner Problem, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.559-570, February 27-March 01, 1997
• 28: 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]
• 29: J. S. Provan, Convexity and the Steiner tree problem, Networks, v.18 n.1, p.55-72, Spring 1988 [doi>10.1002/net.3230180108]
• 30: 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]
• 31: Gabriel Robins , Alexander Zelikovsky, Tighter Bounds for Graph Steiner Tree Approximation, SIAM Journal on Discrete Mathematics, v.19 n.1, p.122-134, 2005 [doi>10.1137/S0895480101393155]
• 32: Sommerville, D. 1929. An Introduction to the Geometry of n Dimensions. London.
• 33: Takahashi, H., and Matsuyama, A. 1980. An approximate solution for the Steiner problem in graphs. Math. Japonicae 24, 571--577.
• 34: Tazari, S., and Müller-Hannemann, M. 2008. To fear or not to fear large hidden constants: Implementing a planar Steiner tree PTAS. Tech. rep. TUD-CD-2008-2, Technische Universität Darmstadt, Department of Computer Science, Darmstadt, Germany.
• 35: Whitney, H. 1933. Planar graphs. Fundam. Math. 21, 73--84.
• 36: 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
• 37: 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]
• 38: Zelikovsky, A. 1993. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463--470.
• 39: Alexander Zelikovsky, Better approximation bounds for the network and Euclidean Steiner tree problems, University of Virginia, Charlottesville, VA, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Steiner tree, approximation scheme, planar graphs