{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T03:18:50Z","timestamp":1784949530583,"version":"3.55.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,7,14]],"date-time":"2016-07-14T00:00:00Z","timestamp":1468454400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s12532-016-0110-1","type":"journal-article","created":{"date-parts":[[2016,7,14]],"date-time":"2016-07-14T09:54:12Z","timestamp":1468490052000},"page":"135-202","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm"],"prefix":"10.1007","volume":"9","author":[{"given":"Stefan","family":"Hougardy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jannik","family":"Silvanus","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,7,14]]},"reference":[{"key":"110_CR1","unstructured":"11th DIMACS implementation challenge (2014). http:\/\/dimacs11.zib.de\/downloads.html . Accessed 5 July 2016"},{"key":"110_CR2","doi-asserted-by":"crossref","unstructured":"de\u00a0Arag\u00e3o, M.P., Uchoa, E., Werneck, R.F.: Dual heuristics on the exact solution of large Steiner problems. Electron. Notes Discrete Math. 7, 150\u2013153 (2001)","DOI":"10.1016\/S1571-0653(04)00247-1"},{"key":"110_CR3","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J Beasley","year":"1984","unstructured":"Beasley, J.: An algorithm for the Steiner problem in graphs. Networks 14, 147\u2013159 (1984)","journal-title":"Networks"},{"key":"110_CR4","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: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 7965, pp. 196\u2013207. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-39206-1_17"},{"issue":"1","key":"110_CR5","doi-asserted-by":"crossref","first-page":"6:1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1\u20136:33 (2013)","journal-title":"J. ACM"},{"issue":"3","key":"110_CR6","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci. 406(3), 207\u2013214 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"110_CR7","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1287\/ijoc.4.3.320","volume":"4","author":"S Chopra","year":"1992","unstructured":"Chopra, S., Gorres, E., Rao, M.: Solving the Steiner tree problem on a graph using branch and cut. ORSA J. Comput. 4, 320\u2013335 (1992)","journal-title":"ORSA J. Comput."},{"key":"110_CR8","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"3","key":"110_CR9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195\u2013207 (1971)","journal-title":"Networks"},{"key":"110_CR10","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0167-6377(89)90005-9","volume":"8","author":"C Duin","year":"1989","unstructured":"Duin, C., Volgenant, A.: An edge elimination test for the Steiner problem in graphs. Oper. Res. Lett. 8, 79\u201383 (1989)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"110_CR11","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"RE Erickson","year":"1987","unstructured":"Erickson, R.E., Monma, C.L., Veinott Jr., A.F.: Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12(4), 634\u2013664 (1987)","journal-title":"Math. Oper. Res."},{"key":"110_CR12","doi-asserted-by":"crossref","unstructured":"Fafianie, S., Bodlaender, H., Nederlof, J.: Speeding up dynamic programming with representative sets. In: Gutin, G., Szeider, S. (eds.) Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 8246, pp. 321\u2013334. Springer International Publishing, New York (2013)","DOI":"10.1007\/978-3-319-03898-8_27"},{"key":"110_CR13","unstructured":"Fonseca, R., Brazil, M., Winter, P., Zachariasen, M.: Faster exact algorithms for computing Steiner trees in higher dimensional euclidean spaces. In: 11th DIMACS Implementation Challenge on Steiner Tree Problems (2014). http:\/\/dimacs11.zib.de\/workshop\/FonsecaBrazilWinterZachariasen.pdf . Accessed 5 July 2016"},{"issue":"3","key":"110_CR14","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"3","key":"110_CR15","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s00224-007-1324-4","volume":"41","author":"B Fuchs","year":"2007","unstructured":"Fuchs, B., Kern, W., M\u00f6lle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theory Comput. Syst. 41(3), 493\u2013500 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"110_CR16","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(2), 255\u2013265 (1966)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"110_CR17","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"SSC\u20134","author":"PE Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. SSC\u20134(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"issue":"1","key":"110_CR18","doi-asserted-by":"publisher","first-page":"196","DOI":"10.2307\/2098806","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962). doi: 10.2307\/2098806","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"110_CR19","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M Held","year":"1970","unstructured":"Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees. Oper. Res. 18, 1138\u20131162 (1970)","journal-title":"Oper. Res."},{"key":"110_CR20","unstructured":"Held, S., Korte, B., Rautenbach, D., Vygen, J.: Combinatorial optimization in VLSI design. In: Combinatorial Optimization\u2014methods and applications, pp. 33\u201396. IOS Press, Amsterdam (2011)"},{"issue":"1","key":"110_CR21","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"FK Hwang","year":"1976","unstructured":"Hwang, F.K.: On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30(1), 104\u2013114 (1976)","journal-title":"SIAM J. Appl. Math."},{"key":"110_CR22","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., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"110_CR23","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O","volume":"32","author":"T Koch","year":"1998","unstructured":"Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32, 207\u2013232 (1998)","journal-title":"Networks"},{"key":"110_CR24","unstructured":"Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis (2004)"},{"key":"110_CR25","unstructured":"Polzin, T., Vahdati, S.: Extending reduction techniques for the Steiner tree problem: a combination of alternative- and bound-based approaches. Tech. Rep. MPI-I-2001-1-007, Max-Planck-Institut f\u00fcr Informatik (2001)"},{"key":"110_CR26","doi-asserted-by":"crossref","unstructured":"Polzin, T., Vahdati Daneshmand, S.: Practical partitioning-based methods for the Steiner problem. In: \u00c0lvarez, C., Serna, M. (eds.) Experimental Algorithms, Lecture Notes in Computer Science, vol. 4007, pp. 241\u2013252. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/11764298_22"},{"key":"110_CR27","unstructured":"Polzin, T., Vahdati Daneshmand, S.: The Steiner Tree Challenge: An updated Study (2014). http:\/\/dimacs11.zib.de\/papers\/PolzinVahdatiDIMACS.pdf . Accessed 5 July 2016"},{"key":"110_CR28","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Technol. J. 36, 1389\u20131401 (1957)","journal-title":"Bell Syst. Technol. J."},{"key":"110_CR29","unstructured":"Silvanus, J.: Fast exact Steiner tree generation using dynamic programming. Master\u2019s thesis, Research Institute for Discrete Mathematics, University of Bonn (2013)"},{"issue":"1","key":"110_CR30","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1137\/0221013","volume":"21","author":"TL Snyder","year":"1992","unstructured":"Snyder, T.L.: On the exact location of Steiner points in general dimension. SIAM J. Comput. 21(1), 163\u2013180 (1992)","journal-title":"SIAM J. Comput."},{"key":"110_CR31","unstructured":"Uchoa, E., de\u00a0Arag\u00e3o, M., Ribeiro, C.: Preprocessing Steiner problems from VLSI layout. Tech. Rep. MCC 32\/99, Catholic University of Rio de Janeiro, Rio de Janeiro (1999)"},{"key":"110_CR32","unstructured":"Vahdati Daneshmand, S.: Algorithmic approaches to the Steiner problem in networks. Ph.D. thesis (2004)"},{"issue":"21\u201322","key":"110_CR33","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1016\/j.ipl.2011.08.005","volume":"111","author":"J Vygen","year":"2011","unstructured":"Vygen, J.: Faster algorithm for optimum Steiner trees. Inf. Process. Lett. 111(21\u201322), 1075\u20131079 (2011)","journal-title":"Inf. Process. Lett."},{"key":"110_CR34","volume-title":"Exact algorithms for plane Steiner tree problems: A computational study","author":"DM Warme","year":"2000","unstructured":"Warme, D.M., Winter, P., Zachariasen, M.: Exact algorithms for plane Steiner tree problems: A computational study. Springer, New York (2000)"},{"issue":"3","key":"110_CR35","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"R Wong","year":"1984","unstructured":"Wong, R.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28(3), 271\u2013287 (1984)","journal-title":"Math. Program."},{"key":"110_CR36","unstructured":"Wulff-Nilsen, C.: Higher dimensional rectilinear Steiner minimal trees. Master\u2019s thesis, Department of Computer Science, University of Copenhagen (2006)"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-016-0110-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0110-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0110-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0110-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T04:16:09Z","timestamp":1568175369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-016-0110-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,14]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["110"],"URL":"https:\/\/doi.org\/10.1007\/s12532-016-0110-1","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,14]]}}}