Improved Steiner tree algorithms for bounded treewidth

Arnborg, 1987, Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 277, 10.1137/0608024 Bateni, 2011, Prize-collecting Steiner problems on planar graphs, 1028 Bateni, 2010, Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth, 211 Bateni Berend, 2010, Improved bounds on Bell numbers and on moments of sums of random variables, Probability and Mathematical Statistics, 30, 185 Bern, 1991, Polynomially solvable special cases of the Steiner problem in planar networks, Annals of Operations Research, 33, 403, 10.1007/BF02071979 Bern, 1987, Linear-time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 216, 10.1016/0196-6774(87)90039-3 Bern, 1989, The Steiner problem with edge lengths 1 and 2, Information Processing Letters, 32, 171, 10.1016/0020-0190(89)90039-2 N. Betzler, Steiner tree problems in the analysis of biological networks, Masterʼs thesis, Universität Tübingen, 2006. Björklund, 2007, Fourier meets Möbius: Fast subset convolution, 67 Bodlaender, 1993, A tourist guide through treewidth, Acta Cybernetica, 11, 1 Bodlaender, 1996, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305, 10.1137/S0097539793251219 Bodlaender, 2007, Treewidth: Structure and algorithms, vol. 4474, 11 Borradaile, 2007, A polynomial-time approximation scheme for Steiner tree in planar graphs, 1285 Borradaile, 2009, An O(nlogn) approximation scheme for Steiner tree in planar graphs, ACM Transactions on Algorithms, 5, 1, 10.1145/1541885.1541892 Chekuri Cygan, 2011, Solving connectivity problems parameterized by treewidth in single exponential time, 150 Downey, 1999 Dreyfus, 1972, The Steiner problem in graphs, Networks, 1, 195, 10.1002/net.3230010302 Erickson, 1987, Send-and-split method for minimum-concave-cost network flows, Mathematics of Operations Research, 12, 634, 10.1287/moor.12.4.634 Garey, 1977, The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32, 826, 10.1137/0132071 Gassner, 2010, The Steiner forest problem revisited, J. Discrete Algorithms, 8, 154, 10.1016/j.jda.2009.05.002 Kloks, 1994, Treewidth, Computations and Approximations, vol. 842 E. Korach, N. Solel, Linear time algorithm for minimum weight Steiner tree in graphs with bounded treewidth, Technical Report 632, Israel Institute of Technology, 1990. Niedermeier, 2006 Polzin, 2006, Practical partitioning-based methods for the Steiner problem, vol. 4007, 241 Ravi, 1994, Spanning trees short or small, 546 Riordan, 1980 Robertson, 1986, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309, 10.1016/0196-6774(86)90023-4 J.A. Wald, C.J. Colbourn, Steiner trees in outerplanar graphs, in: Thirteenth Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1982, pp. 15–22. Wald, 1983, Steiner trees, partial 2-trees and minimum IFI networks, Networks, 13, 159, 10.1002/net.3230130202