{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T13:34:24Z","timestamp":1782912864936,"version":"3.54.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2005,10,12]],"date-time":"2005-10-12T00:00:00Z","timestamp":1129075200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2006,2]]},"DOI":"10.1007\/s10107-005-0660-x","type":"journal-article","created":{"date-parts":[[2005,10,12]],"date-time":"2005-10-12T15:10:17Z","timestamp":1129129817000},"page":"427-449","source":"Crossref","is-referenced-by-count":172,"title":["An Algorithmic Framework for the Exact Solution of the Prize-Collecting Steiner Tree Problem"],"prefix":"10.1007","volume":"105","author":[{"given":"Ivana","family":"Ljubi\u0107","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ren\u00e9","family":"Weiskircher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ulrich","family":"Pferschy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matteo","family":"Fischetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,10,12]]},"reference":[{"key":"660_CR1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"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":"660_CR2","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1023\/A:1027314121992","volume":"3","author":"Bachhiesl","year":"4","unstructured":"Bachhiesl, P., Prossegger, M., Paulus, G., Werner, J., St\u00f6gner, H.: Simulation and optimization of the implementation costs for the last mile of fiber optic networks. Networks and Spatial Economics 3 (4), 467\u2013482 (2003)","journal-title":"Networks and Spatial Economics"},{"key":"660_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230190102","volume":"19","author":"Beasley","year":"1989","unstructured":"Beasley, J.E.: An SST-based algorithm for the Steiner problem in graphs. Networks 19, 1\u201316 (1989)","journal-title":"Networks"},{"key":"660_CR4","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.: A note on the prize-collecting traveling salesman problem. Mathematical Programming 59, 413\u2013420 (1993)","journal-title":"Mathematical Programming"},{"key":"660_CR5","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/net.1023","volume":"38","author":"Canuto","year":"2001","unstructured":"Canuto, S.A., Resende, M.G.C., Ribeiro, C.C.: Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks 38, 50\u201358 (2001)","journal-title":"Networks"},{"key":"660_CR6","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/PL00009180","volume":"19","author":"Cherkassky","year":"1997","unstructured":"Cherkassky, B.V., Goldberg, A.V.: On implementing push-relabel method for the maximum flow problem. Algorithmica 19, 390\u2013410 (1997)","journal-title":"Algorithmica"},{"key":"660_CR7","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1287\/ijoc.4.3.320","volume":"4","author":"Chopra","year":"1992","unstructured":"Chopra, S., Gorres, E., Rao, M.R.: Solving a Steiner tree problem on a graph using a branch and cut. ORSA Journal on Computing, 4, 320\u2013335 (1992)","journal-title":"ORSA Journal on Computing,"},{"key":"660_CR8","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01582573","volume":"64","author":"Chopra","year":"1994","unstructured":"Chopra, S., Rao, M.R.: The Steiner tree problem I: Formulations, compositions and extension of facets. Mathematical Programming 64, 209\u2013229 (1994)","journal-title":"Mathematical Programming"},{"key":"660_CR9","unstructured":"Dongarra, J.J.: Performance of various computers using standard linear equations software (linpack benchmark report). Technical Report CS-89-85, University of Tennessee, 2004"},{"key":"660_CR10","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1002\/net.3230170309","volume":"17","author":"Duin","year":"2","unstructured":"Duin, C.W., Volgenant, A.: Some generalizations of the Steiner problem in graphs. Networks 17 (2), 353\u2013364 (1987)","journal-title":"Networks"},{"key":"660_CR11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/(SICI)1097-0037(199801)31:1<11::AID-NET2>3.0.CO;2-N","volume":"31","author":"Engevall","year":"1","unstructured":"Engevall, S., G\u00f6the-Lundgren, M., V\u00e4rbrand, P.: A strong lower bound for the node weighted Steiner tree problem. Networks 31 (1), 11\u201317 (1998)","journal-title":"Networks"},{"key":"660_CR12","unstructured":"Feofiloff, P., Fernandes, C.G., Ferreira, C.E., Pina, J.C.: Primal-dual approximation algorithms for the prize-collecting Steiner tree problem. 2003 (submitted)"},{"key":"660_CR13","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BF01586946","volume":"51","author":"Fischetti","year":"1991","unstructured":"Fischetti, M.: Facets of two Steiner arborescence polyhedra. Mathematical Programming 51, 401\u2013419 (1991)","journal-title":"Mathematical Programming"},{"key":"660_CR14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01582064","volume":"63","author":"Goemans","year":"1994","unstructured":"Goemans, M.X.: The Steiner tree polytope and related polyhedra. Mathematical Programming 63, 157\u2013182 (1994)","journal-title":"Mathematical Programming"},{"key":"660_CR15","unstructured":"Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum, D.S. (ed) Approximation algorithms for NP-hard problems, P. W. S. Publishing Co., 1996, pp 144\u2013191"},{"key":"660_CR16","unstructured":"Gutin, G., Punnen, A. (eds) The traveling salesman problem and its variations. Kluwer, 2002"},{"key":"660_CR17","unstructured":"Hackner, J.: Energiewirtschaftlich optimale Ausbauplanung kommunaler Fernw\u00e4rmesysteme. PhD thesis, Vienna University of Technology, Austria, 2004"},{"key":"660_CR18","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize-collecting Steiner tree problem: Theory and practice. In: Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 2000, pp 760\u2013769"},{"key":"660_CR19","doi-asserted-by":"crossref","unstructured":"Klau, G.W., Ljubi\u0107, I., Moser, A., Mutzel, P., Neuner, P., Pferschy, U., Weiskircher, R.: Combining a memetic algorithm with integer programming to solve the prize-collecting Steiner tree problem. In: Deb, K. (ed), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), volume 3102 of LNCS, Springer-Verlag, 2004, pp 1304\u20131315","DOI":"10.1007\/978-3-540-24854-5_125"},{"key":"660_CR20","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":"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":"660_CR21","unstructured":"Ljubi\u0107, I., Weiskircher, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: Solving the prize-collecting Steiner tree problem to optimality. In: Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 05). SIAM, 2005 (to appear)"},{"key":"660_CR22","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0166-218X(03)00380-9","volume":"141","author":"Lucena","year":"2004","unstructured":"Lucena, A., Resende, M.G.C.: Strong lower bounds for the prize-collecting Steiner problem in graphs. Discrete Applied Mathematics 141, 277\u2013294 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"660_CR23","unstructured":"Minkoff, M.: The prize-collecting Steiner tree problem. Master's thesis, MIT, May, 2000"},{"key":"660_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230170102","volume":"17","author":"Segev","year":"1987","unstructured":"Segev, A.: The node-weighted Steiner tree problem. Networks 17, 1\u201317 (1987)","journal-title":"Networks"},{"key":"660_CR25","unstructured":"Uchoa, E.: Reduction tests for the prize-collecting Steiner problem. Technical Report RPEP Vol.4 no.18, Universidade Federal Fluminense, Engenharia de Produ\u00e7\u00e3o, Niter\u00f3i, Brazil, 2004"},{"key":"660_CR26","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"Wong","year":"1984","unstructured":"Wong, R.T.: A dual ascent based approach for the Steiner tree problem in directed graphs. Mathematical Programming 28, 271\u2013287 (1984)","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0660-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-005-0660-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0660-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:49:59Z","timestamp":1559123399000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-005-0660-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10,12]]},"references-count":26,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2006,2]]}},"alternative-id":["660"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0660-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10,12]]}}}