{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T03:56:01Z","timestamp":1754020561660,"version":"3.41.2"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,9,19]],"date-time":"2018-09-19T00:00:00Z","timestamp":1537315200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,9,19]],"date-time":"2018-09-19T00:00:00Z","timestamp":1537315200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"FCT - Portuguese Foundation for Science and Technology","award":["SFRH\/BD\/46394\/2008","UID\/MAT\/04106\/2013"],"award-info":[{"award-number":["SFRH\/BD\/46394\/2008","UID\/MAT\/04106\/2013"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper Res Int J"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s12351-018-0426-x","type":"journal-article","created":{"date-parts":[[2018,9,19]],"date-time":"2018-09-19T05:15:29Z","timestamp":1537334129000},"page":"2467-2495","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient lower and upper bounds for the weight-constrained minimum spanning tree problem using simple Lagrangian based algorithms"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0529-5090","authenticated-orcid":false,"given":"Cristina","family":"Requejo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8069-2657","authenticated-orcid":false,"given":"Eul\u00e1lia","family":"Santos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,19]]},"reference":[{"key":"426_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0305-0548(82)90026-0","volume":"9","author":"V Aggarwal","year":"1982","unstructured":"Aggarwal V, Aneja YP, Nair KPK (1982) Minimal spanning tree subject to a side constraint. Comput Oper Res 9:287\u2013296","journal-title":"Comput Oper Res"},{"key":"426_CR2","doi-asserted-by":"crossref","unstructured":"Agra A, Cerveira A, Requejo C, Santos E (2011) On the weight-constrained minimum spanning tree problem. In: Proceedings of the international network optimization conference, volume 6701 of lecture notes in computer science, pp 156\u2013161","DOI":"10.1007\/978-3-642-21527-8_20"},{"issue":"3","key":"426_CR3","doi-asserted-by":"publisher","first-page":"1111","DOI":"10.1007\/s10878-014-9812-3","volume":"31","author":"A Agra","year":"2016","unstructured":"Agra A, Requejo C, Santos E (2016) Implicit cover inequalities. J Comb Optim 31(3):1111\u20131129","journal-title":"J Comb Optim"},{"key":"426_CR4","volume-title":"Network flows: theory, algorithms and applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms and applications. Prentice-Hall, Upper Saddle River"},{"key":"426_CR5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0377-2217(95)00248-0","volume":"95","author":"L Amado","year":"1996","unstructured":"Amado L, B\u00e1rcia P (1996) New polynomial bounds for matroidal knapsacks. Eur J Oper Res 95:201\u2013210","journal-title":"Eur J Oper Res"},{"key":"426_CR6","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1016\/S0305-0548(96)00026-3","volume":"23","author":"K Andersen","year":"1996","unstructured":"Andersen K, J\u00f6rnsten K, Lind M (1996) On bicriterion minimal spanning trees: an approximation. Comput Oper Res 23:1171\u20131182","journal-title":"Comput Oper Res"},{"key":"426_CR7","first-page":"157","volume":"14","author":"D Blokh","year":"1996","unstructured":"Blokh D, Gutin G (1996) An approximation algorithm for combinatorial optimization problems with two parameters. Australas J Comb 14:157\u2013164","journal-title":"Australas J Comb"},{"issue":"2","key":"426_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan ED, Mor\u00e9 JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201\u2013213","journal-title":"Math Program"},{"key":"426_CR9","unstructured":"FICO Xpress optimization suite (2012) http:\/\/www.fico.com\/en\/products\/fico-xpress-optimization-suite"},{"issue":"2","key":"426_CR10","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2950048","volume":"43","author":"N Gould","year":"2016","unstructured":"Gould N, Scott J (2016) A note on performance profiles for benchmarking software. ACM Trans Math Softw 43(2):15:1\u201315:5","journal-title":"ACM Trans Math Softw"},{"key":"426_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02032304","volume":"52","author":"H Hamacher","year":"1994","unstructured":"Hamacher H, Ruhe G (1994) On spanning tree problems with multiple objectives. Ann Oper Res 52:209\u2013230","journal-title":"Ann Oper Res"},{"key":"426_CR12","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/net.3230100403","volume":"10","author":"G Handler","year":"1980","unstructured":"Handler G, Zang I (1980) A dual algorithm for the constrained shortest path problem. Networks 10:293\u2013310","journal-title":"Networks"},{"issue":"4","key":"426_CR13","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1080\/00150517.1981.12430071","volume":"19","author":"R Hassin","year":"1981","unstructured":"Hassin R (1981) On maximizing functions by Fibonacci search. Fibonacci Q 19(4):347\u2013351","journal-title":"Fibonacci Q"},{"issue":"2","key":"426_CR14","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1137\/S0097539703426775","volume":"33","author":"R Hassin","year":"2004","unstructured":"Hassin R, Levin A (2004) An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM J Comput 33(2):261\u2013268","journal-title":"SIAM J Comput"},{"key":"426_CR15","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M Held","year":"1974","unstructured":"Held M, Wolfe P, Crowder H (1974) Validation of subgradient optimization. Math Program 6:62\u201388","journal-title":"Math Program"},{"key":"426_CR16","unstructured":"Henn S (2007) Weight-constrained minimum spanning tree problem. Master\u2019s thesis, University of Kaiserslautern, Kaiserslautern, Germany"},{"key":"426_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.orl.2003.06.003","volume":"32","author":"S Hong","year":"2004","unstructured":"Hong S, Chung S, Park BH (2004) A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. Oper Res Lett 32:233\u2013239","journal-title":"Oper Res Lett"},{"issue":"4","key":"426_CR18","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1080\/02331938808843366","volume":"19","author":"K J\u00f6rnsten","year":"1988","unstructured":"J\u00f6rnsten K, Migdalas S (1988) Designing a minimal spanning tree network subject to a budget constraint. Optimization 19(4):475\u2013484","journal-title":"Optimization"},{"key":"426_CR19","doi-asserted-by":"crossref","unstructured":"J\u00fcttner A, Szviatovszki B, M\u00e9cs I, Rajk\u00f3 Z (2001) Lagrange relaxation based method for the QoS routing problem. In: 20th Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings IEEE INFOCOM 2001, pp 859\u2013868","DOI":"10.1109\/INFCOM.2001.916277"},{"key":"426_CR20","first-page":"503","volume-title":"Network models, handbooks in operations research and management science","author":"TL Magnanti","year":"1995","unstructured":"Magnanti TL, Wolsey LA (1995) Optimal trees. In: Ball M, Magnanti TL, Monma C, Nemhauser GL (eds) Network models, handbooks in operations research and management science, vol 7. Elsevier Science Publishers, North-Holland, pp 503\u2013615"},{"key":"426_CR21","doi-asserted-by":"crossref","unstructured":"Mehlhorn K, Ziegelmann M (2001) CNOP\u2014a package for constrained network optimization. In: Buchsbaum A, Snoeyink J (eds) Algorithm engineering and experimentation, vol 2153. Lecture Notes in Computer Science. Springer, Berlin\/Heidelberg, pp 17\u201331","DOI":"10.1007\/3-540-44808-X_2"},{"issue":"9","key":"426_CR22","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1016\/j.cor.2004.03.002","volume":"32","author":"D Pisinger","year":"2005","unstructured":"Pisinger D (2005) Where are the hard knapsack problems? Comput Oper Res 32(9):2271\u20132284","journal-title":"Comput Oper Res"},{"key":"426_CR23","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/S0377-2217(97)00391-3","volume":"111","author":"R Ramos","year":"1998","unstructured":"Ramos R, Alonso S, Sicilia J, Gonz\u00e1lez C (1998) The problem of the optimal biobjective spanning tree. Eur J Oper Res 111:617\u2013628","journal-title":"Eur J Oper Res"},{"key":"426_CR24","doi-asserted-by":"crossref","unstructured":"Ravi R, Goemans M (1996) The constrained minimum spanning tree problem. In: Proceedings of the Scandinavian workshop on algorithmic theory, volume 1097 of Lecture Notes in Computer Science, pp 66\u201375","DOI":"10.1007\/3-540-61422-2_121"},{"key":"426_CR25","doi-asserted-by":"crossref","unstructured":"Requejo C, Agra A, Cerveira A, Santos E (2010) Formulations for the weight-constrained minimum spanning tree problem. In: Proceedings of the international conference on numerical analysis and applied mathematics, volume 1281 of AIP conference proceedings, pp 2166\u20132169","DOI":"10.1063\/1.3498397"},{"key":"426_CR26","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1002\/net.3230130203","volume":"13","author":"A Shogan","year":"1983","unstructured":"Shogan A (1983) Constructing a minimal-cost spanning tree subject to resource constraints and flow requirements. Networks 13:169\u2013190","journal-title":"Networks"},{"key":"426_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82118-9","volume-title":"Minimization methods for non-differentiable functions","author":"N Shor","year":"1985","unstructured":"Shor N (1985) Minimization methods for non-differentiable functions. Springer, Berlin"},{"issue":"3","key":"426_CR28","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1287\/ijoc.1070.0260","volume":"20","author":"F Sourd","year":"2008","unstructured":"Sourd F, Spanjaard O (2008) A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem. INFORMS J Comput 20(3):472\u2013484","journal-title":"INFORMS J Comput"},{"issue":"1","key":"426_CR29","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.cor.2006.02.023","volume":"35","author":"S Steiner","year":"2008","unstructured":"Steiner S, Radzik T (2008) Computing all efficient solutions of the biobjective minimum spanning tree problem. Comput Oper Res 35(1):198\u2013211","journal-title":"Comput Oper Res"},{"issue":"2","key":"426_CR30","first-page":"63","volume":"2","author":"Y Xiao","year":"2005","unstructured":"Xiao Y, Thulasiraman K, Xue G, J\u00fcttner A (2005) The constrained shortest path problem: algorithmic approaches and an algebraic study with generalization. AKCE Int J Graphs Comb 2(2):63\u201386","journal-title":"AKCE Int J Graphs Comb"},{"key":"426_CR31","unstructured":"Xue G (2000) Primal-dual algorithms for computing weight-constrained shortest paths and weight-constrained minimum spanning trees. In: IEEE international conference on performance, computing, and communications proceedings IEEE IPCCC \u201900, pp 271\u2013277"},{"issue":"5","key":"426_CR32","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1109\/TCOMM.2003.811420","volume":"51","author":"G Xue","year":"2003","unstructured":"Xue G (2003) Minimum-cost QoS multicast and unicast routing in communication networks. IEEE Trans Commun 51(5):817\u2013824","journal-title":"IEEE Trans Commun"},{"key":"426_CR33","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/00207160412331290667","volume":"82","author":"T Yamada","year":"2005","unstructured":"Yamada T, Watanabe K, Kataoka S (2005) Algorithms to solve the knapsack constrained maximum spanning tree problem. Int J Comput Math 82:23\u201334","journal-title":"Int J Comput Math"}],"container-title":["Operational Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-018-0426-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12351-018-0426-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-018-0426-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T20:43:33Z","timestamp":1751921013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12351-018-0426-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,19]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["426"],"URL":"https:\/\/doi.org\/10.1007\/s12351-018-0426-x","relation":{},"ISSN":["1109-2858","1866-1505"],"issn-type":[{"type":"print","value":"1109-2858"},{"type":"electronic","value":"1866-1505"}],"subject":[],"published":{"date-parts":[[2018,9,19]]},"assertion":[{"value":"28 November 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}