{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T01:07:49Z","timestamp":1725757669679},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_27","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T02:57:26Z","timestamp":1384829846000},"page":"321-334","source":"Crossref","is-referenced-by-count":3,"title":["Speeding Up Dynamic Programming with Representative Sets"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Fafianie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"Y.P. Aneja","year":"1980","unstructured":"Aneja, Y.P.: An integer linear programming approach to the Steiner problem in graphs. Networks\u00a010, 167\u2013178 (1980)","journal-title":"Networks"},{"key":"27_CR2","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J.E. Beasley","year":"1984","unstructured":"Beasley, J.E.: An algorithm for the Steiner problem in graphs. Networks\u00a014, 147\u2013159 (1984)","journal-title":"Networks"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming algorithms on graphs with bounded tree-width. In: Lepist\u00f6, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol.\u00a0317, pp. 105\u2013119. Springer, Heidelberg (1988)"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-39206-1_17","volume-title":"Automata, Languages, and Programming","author":"H.L. Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 196\u2013207. Springer, Heidelberg (2013)"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Information and Computation\u00a0208, 259\u2013275 (2010)","journal-title":"Information and Computation"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. 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\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"27_CR8","doi-asserted-by":"publisher","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. Journal of Discrete Algorithms\u00a016, 67\u201378 (2012)","journal-title":"Journal of Discrete Algorithms"},{"issue":"3","key":"27_CR9","doi-asserted-by":"publisher","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 Journal on Computing\u00a015(3), 233\u2013248 (2003)","journal-title":"INFORMS Journal on Computing"},{"key":"27_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":"27_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":"27_CR12","unstructured":"Duin, C.: Steiner Problems in Graphs. PhD thesis, University of Amsterdam, Amsterdam, the Netherlands (1993)"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Fafianie, S., Bodlaender, H.L., Nederlof, J.: Speeding-up dynamic programming with representative sets \u2014 an experimental evaluation of algorithms for Steiner tree on tree decompositions. Report on arXiv 1305.7448 (2013)","DOI":"10.1007\/978-3-319-03898-8_27"},{"key":"27_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. Report on arXiv 1304.4626 (2013)","DOI":"10.1137\/1.9781611973402.10"},{"key":"27_CR15","doi-asserted-by":"publisher","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. Applied Math.\u00a014, 255\u2013265 (1966)","journal-title":"SIAM J. Applied Math."},{"key":"27_CR16","unstructured":"Hwang, F., Richards, D.S., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics, vol.\u00a053. Elsevier (1992)"},{"key":"27_CR17","doi-asserted-by":"crossref","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 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"27_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-37, Konrad-Zuse Zentrum f\u00fcr Informationstechnik Berlin (2000), http:\/\/elib.zib.de\/steinlib","DOI":"10.1007\/978-1-4613-0255-1_9"},{"key":"27_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":"27_CR21","unstructured":"Lov\u00e1sz, L.: Flats in matroids and geometric graphs. In: Combinatorial Surveys. Proceedings 6th Britisch Combinatorial Conference, pp. 45\u201386. Academic Press (1977)"},{"key":"27_CR22","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0410, 4471\u20134479 (2009)","journal-title":"Theoretical Computer Science"},{"key":"27_CR23","first-page":"239","volume":"25","author":"B. Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Annals of Discrete Mathematics\u00a025, 239\u2013254 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"27_CR24","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. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"27_CR25","doi-asserted-by":"publisher","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-trees. Discrete Applied Mathematics\u00a044, 109\u2013117 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR26","unstructured":"Treewidthlib (2004), http:\/\/www.cs.uu.nl\/people\/hansb\/treewidthlib"},{"key":"27_CR27","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"J.A. Wald","year":"1983","unstructured":"Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks\u00a013, 159\u2013167 (1983)","journal-title":"Networks"},{"key":"27_CR28","unstructured":"Warme, D., Winter, P., Zachariasen, M.: GeoSteiner, software for computing Steiner trees, http:\/\/www.diku.dk\/hjemmesider\/ansatte\/martinz\/geosteiner\/"},{"key":"27_CR29","unstructured":"Wei-Kleiner, F.: Tree decomposition based Steiner tree computation over large graphs. Report on arXiv 1305.5757 (2013)"},{"key":"27_CR30","doi-asserted-by":"publisher","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\u00a017, 129\u2013167 (1987)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03898-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,8]],"date-time":"2020-08-08T09:25:29Z","timestamp":1596878729000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_27"}},"subtitle":["An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions"],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}