Glencora Borradaile
Philip Klein
Skip Abstract Section
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).
- Arora, S. 1998. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J. ACM 45, 5, 753--782. Google Scholar
Digital Library
- Arora, S., Grigni, M., Karger, D., Klein, P., and Woloszyn, A. 1998. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. 33--41. Google ScholarDigital Library
- Baker, B. 1994. Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 1, 153--180. Google ScholarDigital Library
- Berman, P., and Ramaiyer, V. 1994. Improved approximations for the Steiner tree problem. J. Algor. 17, 381--408. Google ScholarDigital Library
- Bern, M. 1990. Faster exact algorithms for Steiner trees in planar networks. Netw. 20, 109--120.Google ScholarCross Ref
- Bern, M., and Bienstock, D. 1991. Polynomially solvable special cases of the Steiner problem in planar networks. Math. Oper. Res. 33, 405--418.Google Scholar
- Bern, M., and Plassmann, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32, 171--176. Google ScholarDigital Library
- Borradaile, G., Kenyon-Mathieu, C., and Klein, P. 2007a. A polynomial-time approximation scheme for Steiner tree in planar graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1285--1294. Google ScholarDigital Library
- Borradaile, G., and Klein, P. 2008. The two-edge connectivity survivable network problem in planar graphs. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Catalan, E. 1838. Note sur un problème de combinaisons. J. Mathématiques Pures et Appl. 3, 111 --112.Google Scholar
- Demaine, E. D., and Hajiaghayi, M. 2005. Bidimensionality: New connections between FPT algorithms and PTASs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 367--376. Google ScholarDigital Library
- Erickson, R., Monma, C., and Veinott, A. 1987. Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12, 634--664. Google ScholarDigital Library
- Garey, M., and Johnson, D. S. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 4, 826--834.Google ScholarDigital Library
- Henzinger, M. R., Klein, P. N., Rao, S., and Subramanian, S. 1997. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 1, 3--23. Google ScholarDigital Library
- Hopcroft, J., and Tarjan, R. 1974. Efficient planarity testing. J. ACM 21, 4, 549--568. Google ScholarDigital Library
- Hougardy, S., and Prömel, H. J. 1999. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 448--453. Google ScholarDigital Library
- Karp, R. 1975. On the computational complexity of combinatorial problems. Netw. 5, 45--68.Google ScholarDigital Library
- Karpinski, M., and Zelikovsky, A. 1997. New approximation algorithms for the Steiner tree problem. J. Combin. Optimiz. 1, 47--65.Google ScholarCross Ref
- Klein, P. A linear-time approximation scheme for planar TSP. SIAM J. Comput. to appear.Google Scholar
- Klein, P. 2006. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 749--756. Google ScholarDigital Library
- Klein, P. N. 2005a. A linear-time approximation scheme for planar weighted TSP. In Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 647--656. Google ScholarDigital Library
- Klein, P. N. 2005b. Multiple-source shortest paths in planar graphs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 146--155. Google ScholarDigital Library
- Kou, L., Markowsky, G., and Berman, L. 1981. A fast algorithm for Steiner trees. Acta Inf. 15, 141--145.Google ScholarDigital Library
- Mehlhorn, K. 1988. A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27, 3, 125--128. Google ScholarDigital Library
- Mitchell, J. 1999. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28, 4, 1298--1309. Google ScholarDigital Library
- Prömel, H., and Steger, A. 1997. RNC approximation algorithms for the Steiner problem. In Proceedings of the 14th International Symposium on Theoretical Aspects of Computer Science, 559--570. Google ScholarDigital Library
- Provan, J. 1988a. An approximation scheme for finding Steiner trees with obstacles. SIAM J. Comput. 17, 920--934, 920--934. Google ScholarDigital Library
- Provan, J. 1988b. Convexity and the Steiner tree problem. Netw. 18, 55--72. Google ScholarDigital Library
- Rao, S., and Smith, W. 1998. Approximating geometrical graphs via “spanners” and “banyans”. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 540--550. Google ScholarDigital Library
- Robins, G., and Zelikovsky, A. 2005. Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 1, 122--134. Google ScholarDigital Library
- Sommerville, D. 1929. An Introduction to the Geometry of n Dimensions. London.Google Scholar
- Takahashi, H., and Matsuyama, A. 1980. An approximate solution for the Steiner problem in graphs. Math. Japonicae 24, 571--577.Google Scholar
- 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.Google Scholar
- Whitney, H. 1933. Planar graphs. Fundam. Math. 21, 73--84.Google ScholarCross Ref
- Widmayer, P. 1986. A fast approximation algorithm for Steiner's problem in graphs. In Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, vol. 246. Springer Verlag, 17--28. Google ScholarDigital Library
- Wu, Y., Widmayer, P., and Wong, C. 1986. A faster approximation algorithm for the Steiner problem in graphs. Acta Inf. 23, 2, 223--229. Google ScholarDigital Library
- Zelikovsky, A. 1993. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463--470.Google ScholarCross Ref
- Zelikovsky, A. 1994. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. rep. CS-96-06, University of Virginia. Google ScholarDigital Library
Index Terms
- An O(n log n) approximation scheme for Steiner tree in planar graphs
Recommendations
Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices
In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The ...
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees such that each tree contains every ...
Steiner tree in k-star caterpillar convex bipartite graphs: a dichotomy
AbstractA bipartite graph G(X, Y) whose vertex set is partitioned into X and Y is a convex bipartite graph, if there is an ordering of such that for all , is consecutive with respect to the ordering of X, and G is said to have ...
Comments