Abstract
We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in \(\ensuremath{\mathcal{O}(B_{\ensuremath{\textit{tw}}+2}^2 \cdot \ensuremath{\textit{tw}}\ \cdot |V|)}\) time, where \(\ensuremath{\textit{tw}}\) is the graph’s treewidth and the Bell number B k is the number of partitions of a k-element set. This is a linear time algorithm for graphs with fixed treewidth and a polynomial algorithm for \(\ensuremath{\textit{tw}} = \ensuremath{\mathcal{O}(\log|V|/\log\log|V|)}\).
While being faster than the previously known algorithms, our thereby used coloring scheme can be extended to give new, improved algorithms for the prize-collecting Steiner tree as well as the k-cardinality tree problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8(2), 277–284 (1987)
Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M., Korula, N., Marx, D.: Prize-collecting Steiner problems on planar graphs. In: SODA, pp. 1028–1049. SIAM (2011)
Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. In: STOC, pp. 211–220. ACM (2010)
Bateni, M., Hajiaghayi, M., Marx, D.: Prize-collecting network design on planar graphs. CoRR, abs/1006.4339 (2010)
Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics 30, 185–205 (2010)
Bern, M.W., Lawler, E.L., Wong, A.L.: Linear-time computation of optimal subgraphs of decomposable graphs. J. Algorithms 8, 216–235 (1987)
Betzler, N.: Steiner tree problems in the analysis of biological networks. Master’s thesis, Universität Tübingen (2006)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Möbius: Fast subset convolution. In: STOC, pp. 67–74. ACM (2007)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11(1-2), 1–22 (1993)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Bodlaender, H.L.: Treewidth: Structure and Algorithms. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 11–25. Springer, Heidelberg (2007)
Borradaile, G., Kenyon-Mathieu, C., Klein, P.: A polynomial-time approximation scheme for Steiner tree in planar graphs. In: SODA, pp. 1285–1294. SIAM (2007)
Borradaile, G., Klein, P., Mathieu, C.: An O(n logn) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms 5, 1–31 (2009)
Chekuri, C., Ene, A., Korula, N.: Prize-collecting Steiner tree and forest in planar graphs. CoRR, abs/1006.4357 (2010)
Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. CoRR, abs/1103.0534 (2011)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195–207 (1972)
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics 32(4), 826–834 (1977)
Gassner, E.: The Steiner forest problem revisited. J. Discrete Algorithms 8(2), 154–163 (2010)
Korach, E., Solel, N.: Linear time algorithm for minimum weight Steiner tree in graphs with bounded treewidth. Technical Report 632, Israel Institute of Technology (1990)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)
Polzin, T., Daneshmand, S.: Practical Partitioning-Based Methods for the Steiner Problem. In: Àlvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol. 4007, pp. 241–252. Springer, Heidelberg (2006)
Prömel, H.J., Steger, A.: The Steiner Tree Problem. A Tour Through Graphs, Algorithms and Complexity. Vieweg Verlag (2002)
Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees short or small. In: SODA, pp. 546–555. SIAM (1994)
Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chimani, M., Mutzel, P., Zey, B. (2011). Improved Steiner Tree Algorithms for Bounded Treewidth. In: Iliopoulos, C.S., Smyth, W.F. (eds) Combinatorial Algorithms. IWOCA 2011. Lecture Notes in Computer Science, vol 7056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25011-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-25011-8_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25010-1
Online ISBN: 978-3-642-25011-8
eBook Packages: Computer ScienceComputer Science (R0)