{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T03:18:51Z","timestamp":1784949531341,"version":"3.55.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T00:00:00Z","timestamp":1409270400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s00453-014-9934-0","type":"journal-article","created":{"date-parts":[[2014,8,28]],"date-time":"2014-08-28T17:29:09Z","timestamp":1409246949000},"page":"636-660","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Speeding Up Dynamic Programming with Representative Sets: An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions"],"prefix":"10.1007","volume":"71","author":[{"given":"Stefan","family":"Fafianie","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,8,29]]},"reference":[{"key":"9934_CR1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"YP Aneja","year":"1980","unstructured":"Aneja, Y.P.: An integer linear programming approach to the Steiner problem in graphs. Networks 10, 167\u2013178 (1980)","journal-title":"Networks"},{"key":"9934_CR2","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"9934_CR3","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"JE Beasley","year":"1984","unstructured":"Beasley, J.E.: An algorithm for the Steiner problem in graphs. Networks 14, 147\u2013159 (1984)","journal-title":"Networks"},{"key":"9934_CR4","first-page":"105","volume-title":"Proceedings of the 15th International Colloquium on Automata, Languages and Programming, ICALP\u201988, Volume 317 of Lecture Notes in Computer Science","author":"HL Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming algorithms on graphs with bounded tree-width. In: Lepist\u00f6, T., Salomaa, A. (eds.) Proceedings of the 15th International Colloquium on Automata, Languages and Programming, ICALP\u201988, Volume 317 of Lecture Notes in Computer Science, pp. 105\u2013119. Springer, Berlin (1988)"},{"key":"9934_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, Part I, Volume 7965 of Lecture Notes in Computer Science, pp. 196\u2013207. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-39206-1_17"},{"key":"9934_CR6","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inf. Comput. 208, 259\u2013275 (2010)","journal-title":"Inf. Comput."},{"key":"9934_CR7","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"9934_CR8","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.jda.2012.04.016","volume":"16","author":"M Chimani","year":"2012","unstructured":"Chimani, M., Mutzel, P., Zey, B.: Improved Steiner tree algorithms for bounded treewidth. J. Discret. Algorithms 16, 67\u201378 (2012)","journal-title":"J. Discret. Algorithms"},{"issue":"3","key":"9934_CR9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W Cook","year":"2003","unstructured":"Cook, W., Seymour, P.D.: Tour merging via branch-decomposition. INFORMS J. Comput. 15(3), 233\u2013248 (2003)","journal-title":"INFORMS J. Comput."},{"key":"9934_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast Hamiltonicity checking via bases of perfect matchings. In: Proceedings of the 45th Annual Symposium on Theory of Computing, STOC 2013, pp. 301\u2013310 (2013)","DOI":"10.1145\/2488608.2488646"},{"key":"9934_CR11","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. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"9934_CR12","unstructured":"Duin, C.: Steiner problems in graphs. Ph.D. thesis, University of Amsterdam, Amsterdam, The Netherlands (1993)"},{"key":"9934_CR13","doi-asserted-by":"crossref","unstructured":"Fafianie, S., Bodlaender, H.L., Nederlof, J.: Speeding-up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner tree on tree decompositions. Report on arXiv:1305.7448 (2013)","DOI":"10.1007\/s00453-014-9934-0"},{"key":"9934_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact algorithms. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 142\u2013151","DOI":"10.1137\/1.9781611973402.10"},{"key":"9934_CR15","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M Hanan","year":"1966","unstructured":"Hanan, M.: On Steiner\u2019s problem with rectilinear distance. SIAM J. Appl. Math. 14, 255\u2013265 (1966)","journal-title":"SIAM J. Appl. Math."},{"key":"9934_CR16","volume-title":"The Steiner Tree Problem, Volume 53 of Annals of Discrete Mathematics","author":"F Hwang","year":"1992","unstructured":"Hwang, F., Richards, D.S., Winter, P.: The Steiner Tree Problem, Volume 53 of Annals of Discrete Mathematics. Elsevier, Amsterdam (1992)"},{"key":"9934_CR17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013104. Plenum Press, New York (1972)"},{"key":"9934_CR18","volume-title":"Treewidth. Computations and Approximations, Volume 842 of Lecture Notes in Computer Science","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Computations and Approximations, Volume 842 of Lecture Notes in Computer Science. Springer, Berlin (1994)"},{"key":"9934_CR19","doi-asserted-by":"crossref","unstructured":"Koch, T., Martin, A., Vo\u00df, S.: Steinlib, an updated library on Steiner tree problems in graphs. Technical Report ZIB-Report 00\u201337, Konrad-Zuse Zentrum f\u00fcr Informationstechnik Berlin. http:\/\/elib.zib.de\/steinlib (2000)","DOI":"10.1007\/978-1-4613-0255-1_9"},{"key":"9934_CR20","unstructured":"Korach, E., Solel, N.: Linear time algorithm for minimum weight Steiner tree in graphs with bounded treewidth. Technical Report 632, Technion, Haifa, Israel (1990)"},{"key":"9934_CR21","unstructured":"Lov\u00e1sz, L.: Flats in matroids and geometric graphs. In: Combinatorial Surveys. Proceedings 6th Britisch Combinatorial Conference, pp. 45\u201386. Academic Press, London (1977)"},{"key":"9934_CR22","doi-asserted-by":"crossref","first-page":"4471","DOI":"10.1016\/j.tcs.2009.07.027","volume":"410","author":"D Marx","year":"2009","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theoret. Comput. Sci. 410, 4471\u20134479 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"9934_CR23","first-page":"239","volume":"25","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Ann. Discret. Math. 25, 239\u2013254 (1985)","journal-title":"Ann. Discret. Math."},{"key":"9934_CR24","doi-asserted-by":"crossref","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 7, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"9934_CR25","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0166-218X(93)90226-E","volume":"44","author":"J Telle","year":"1993","unstructured":"Telle, J., Proskurowski, A.: Efficient sets in partial $$k$$ k -trees. Discret. Appl. Math. 44, 109\u2013117 (1993)","journal-title":"Discret. Appl. Math."},{"key":"9934_CR26","unstructured":"Treewidthlib. http:\/\/www.cs.uu.nl\/people\/hansb\/treewidthlib (2004)"},{"key":"9934_CR27","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"JA Wald","year":"1983","unstructured":"Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13, 159\u2013167 (1983)","journal-title":"Networks"},{"key":"9934_CR28","unstructured":"Warme, D., Winter, P., Zachariasen, M.: GeoSteiner, software for computing Steiner trees. http:\/\/www.diku.dk\/hjemmesider\/ansatte\/martinz\/geosteiner\/"},{"key":"9934_CR29","unstructured":"Wei-Kleiner, F.: Tree decomposition based Steiner tree computation over large graphs. Report on arXiv:1305.5757 (2013)"},{"key":"9934_CR30","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230170203","volume":"17","author":"P Winter","year":"1987","unstructured":"Winter, P.: Steiner problem in networks: a survey. Networks 17, 129\u2013167 (1987)","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9934-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9934-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9934-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T11:58:19Z","timestamp":1565783899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9934-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,29]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["9934"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9934-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,29]]}}}