{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:13:58Z","timestamp":1742912038570,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642250101"},{"type":"electronic","value":"9783642250118"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25011-8_30","type":"book-chapter","created":{"date-parts":[[2011,11,8]],"date-time":"2011-11-08T20:27:34Z","timestamp":1320784054000},"page":"374-386","source":"Crossref","is-referenced-by-count":3,"title":["Improved Steiner Tree Algorithms for Bounded Treewidth"],"prefix":"10.1007","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernd","family":"Zey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"30_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods\u00a08(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M., Korula, N., Marx, D.: Prize-collecting Steiner problems on planar graphs. In: SODA, pp. 1028\u20131049. SIAM (2011)","DOI":"10.1137\/1.9781611973082.79"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. In: STOC, pp. 211\u2013220. ACM (2010)","DOI":"10.1145\/1806689.1806720"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Marx, D.: Prize-collecting network design on planar graphs. CoRR, abs\/1006.4339 (2010)","DOI":"10.1137\/1.9781611973082.79"},{"key":"30_CR5","first-page":"185","volume":"30","author":"D. Berend","year":"2010","unstructured":"Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics\u00a030, 185\u2013205 (2010)","journal-title":"Probability and Mathematical Statistics"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M.W. Bern","year":"1987","unstructured":"Bern, M.W., Lawler, E.L., Wong, A.L.: Linear-time computation of optimal subgraphs of decomposable graphs. J. Algorithms\u00a08, 216\u2013235 (1987)","journal-title":"J. Algorithms"},{"key":"30_CR7","unstructured":"Betzler, N.: Steiner tree problems in the analysis of biological networks. Master\u2019s thesis, Universit\u00e4t T\u00fcbingen (2006)"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: Fast subset convolution. In: STOC, pp. 67\u201374. ACM (2007)","DOI":"10.1145\/1250790.1250801"},{"issue":"1-2","key":"30_CR9","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica\u00a011(1-2), 1\u201322 (1993)","journal-title":"Acta Cybernetica"},{"issue":"6","key":"30_CR10","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-540-72951-8_3","volume-title":"Structural Information and Communication Complexity","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: Treewidth: Structure and Algorithms. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol.\u00a04474, pp. 11\u201325. Springer, Heidelberg (2007)"},{"key":"30_CR12","unstructured":"Borradaile, G., Kenyon-Mathieu, C., Klein, P.: A polynomial-time approximation scheme for Steiner tree in planar graphs. In: SODA, pp. 1285\u20131294. SIAM (2007)"},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1541885.1541892","volume":"5","author":"G. Borradaile","year":"2009","unstructured":"Borradaile, G., Klein, P., Mathieu, C.: An O(n logn) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms\u00a05, 1\u201331 (2009)","journal-title":"ACM Transactions on Algorithms"},{"key":"30_CR14","unstructured":"Chekuri, C., Ene, A., Korula, N.: Prize-collecting Steiner tree and forest in planar graphs. CoRR, abs\/1006.4357 (2010)"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1109\/FOCS.2011.23"},{"key":"30_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks\u00a01, 195\u2013207 (1972)","journal-title":"Networks"},{"issue":"4","key":"30_CR18","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics\u00a032(4), 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"2","key":"30_CR19","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.jda.2009.05.002","volume":"8","author":"E. Gassner","year":"2010","unstructured":"Gassner, E.: The Steiner forest problem revisited. J. Discrete Algorithms\u00a08(2), 154\u2013163 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"30_CR20","unstructured":"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)"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"30_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/11764298_22","volume-title":"Experimental Algorithms","author":"T. Polzin","year":"2006","unstructured":"Polzin, T., Daneshmand, S.: Practical Partitioning-Based Methods for the Steiner Problem. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol.\u00a04007, pp. 241\u2013252. Springer, Heidelberg (2006)"},{"key":"30_CR23","doi-asserted-by":"crossref","unstructured":"Pr\u00f6mel, H.J., Steger, A.: The Steiner Tree Problem. A Tour Through Graphs, Algorithms and Complexity. Vieweg Verlag (2002)","DOI":"10.1007\/978-3-322-80291-0"},{"key":"30_CR24","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees short or small. In: SODA, pp. 546\u2013555. SIAM (1994)"},{"issue":"3","key":"30_CR25","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25011-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T04:00:48Z","timestamp":1560916848000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25011-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642250101","9783642250118"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25011-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}