{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:32:58Z","timestamp":1761597178452},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,1,7]],"date-time":"2010-01-07T00:00:00Z","timestamp":1262822400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Manag Sci"],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1007\/s10287-009-0116-5","type":"journal-article","created":{"date-parts":[[2010,1,6]],"date-time":"2010-01-06T05:24:24Z","timestamp":1262755464000},"page":"289-311","source":"Crossref","is-referenced-by-count":37,"title":["Reformulations and solution algorithms for the maximum leaf spanning tree problem"],"prefix":"10.1007","volume":"7","author":[{"given":"Abilio","family":"Lucena","sequence":"first","affiliation":[]},{"given":"Nelson","family":"Maculan","sequence":"additional","affiliation":[]},{"given":"Luidi","family":"Simonetti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,1,7]]},"reference":[{"key":"116_CR1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"YP Aneja","year":"1980","unstructured":"Aneja YP (1980) An integer linear programming approach to the Steiner problem in graphs. Networks 10: 167\u2013178","journal-title":"Networks"},{"key":"116_CR2","doi-asserted-by":"crossref","unstructured":"Balasundaram B, Butenko S (2006) Graph domination, coloring and cliques in telecommunications. In: Handbook of optimization in telecommunications. Springer, New York, pp 865\u2013890","DOI":"10.1007\/978-0-387-30165-5_30"},{"key":"116_CR3","unstructured":"Butenko S, Cheng X, Du DZ, Pardalos PM (2002) On the construction of virtual backbone for ad-hoc wireless networks. In: Cooperative control: models, applications and algorithms. Kluwer, Dordrecht, pp 43\u201354"},{"key":"116_CR4","doi-asserted-by":"crossref","unstructured":"Chen S, Ljubi\u0107 I, Raghavan S (2009) The regenerator location problem. Networks (to appear)","DOI":"10.1002\/net.20366"},{"issue":"3","key":"116_CR5","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 MR (1992) Solving Steiner tree problem on a graph using branch and cut. ORSA J Comput 4(3): 320\u2013335","journal-title":"ORSA J Comput"},{"key":"116_CR6","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds J (1971) Matroids and the greedy algorithm. Math Prog 1: 127\u2013136","journal-title":"Math Prog"},{"key":"116_CR7","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/S0377-2217(96)00327-X","volume":"104","author":"ML Fernandes","year":"1998","unstructured":"Fernandes ML, Gouveia L (1998) Minimal spanning trees with a constraint on the number of leaves. Eur J Oper Res 104: 250\u2013261","journal-title":"Eur J Oper Res"},{"key":"116_CR8","doi-asserted-by":"crossref","first-page":"1931","DOI":"10.1016\/S0305-0548(02)00117-X","volume":"30","author":"T Fujie","year":"2003","unstructured":"Fujie T (2003) An exact algorithm for the maximum-leaf spanning tree problem. Comput Oper Res 30: 1931\u20131944","journal-title":"Comput Oper Res"},{"issue":"4","key":"116_CR9","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1002\/net.20001","volume":"43","author":"T Fujie","year":"2004","unstructured":"Fujie T (2004) The maximum-leaf spanning tree problem: formulations and facets. Networks 43(4): 212\u2013223","journal-title":"Networks"},{"key":"116_CR10","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G Galbiati","year":"1994","unstructured":"Galbiati G, Maffioli F, Morzenti A (1994) A short note on the approximability of the maximum leaves spanning tree problem. Info Proc Lett 52: 45\u201349","journal-title":"Info Proc Lett"},{"key":"116_CR11","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, New York"},{"key":"116_CR12","doi-asserted-by":"crossref","unstructured":"Gouveia L, Simonetti L, Uchoa E (2009) Modelling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Math Prog (published online)","DOI":"10.1007\/s10107-009-0297-2"},{"issue":"4","key":"116_CR13","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4): 374\u2013387","journal-title":"Algorithmica"},{"key":"116_CR14","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":"33","author":"T Koch","year":"1998","unstructured":"Koch T, Martin A (1998) Solving Steiner tree problems in graphs to optimality. Networks 33: 207\u2013232","journal-title":"Networks"},{"key":"116_CR15","unstructured":"Lu H, Ravi R (1992) The power of local optimization: approximation algorithms for maximum-leaf spanning tree. In: Thirtieth annual allerton conference on communication, pp 533\u2013542"},{"key":"116_CR16","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jagm.1998.0944","volume":"29","author":"H Lu","year":"1998","unstructured":"Lu H, Ravi R (1998) Approximating maximum leaf spanning trees in almost linear time. J Algo 29: 132\u2013141","journal-title":"J Algo"},{"key":"116_CR17","unstructured":"Lucena A, Maculan N, Simonetti L (2008) Reformulations and solution algorithms for maximum leaf spanning tree problem. In: Abstracts of the VI ALIO\/EURO workshop, pp 48\u201348"},{"key":"116_CR18","unstructured":"Magnanti TL, Wolsey LA (1995) Optimal trees. In: Network models. Handbooks in operations research and management science, vol 7. North Holland, Amsterdam, pp 503\u2013615"},{"key":"116_CR19","unstructured":"Marathe MV, Breu H, Hunt III HB, Ravi SS, Rosenkrantz DJ (1995) Simple heuristics for unit disc graphs. Networks 25"},{"key":"116_CR20","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/S1571-0653(04)00247-1","volume":"7","author":"M Poggi de Arag\u00e3o","year":"2001","unstructured":"Poggi de Arag\u2b60M, Uchoa E, Werneck R (2001) Dual heuristics on the exact solution of large Steiner problems. Electron Notes Discret Math 7:150\u2013153","journal-title":"Electron Notes Discret Math"},{"issue":"1-3","key":"116_CR21","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0166-218X(00)00319-X","volume":"112","author":"T Polzin","year":"2001","unstructured":"Polzin T, Daneshmand SV (2001) Improved algorithms for the Steiner problem in networks. Discret Appl Math 112(1-3): 263\u2013300","journal-title":"Discret Appl Math"},{"key":"116_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-30165-5","volume-title":"Handbook of optimization in telecommunications","author":"MGC Resende","year":"2006","unstructured":"Resende MGC, Pardalos PM (2006) Handbook of optimization in telecommunications. Springer, New York"},{"key":"116_CR23","unstructured":"Simonetti LG (2008) Otimiza\u00e7\u00e3o Combinat\u00f3ria: Problemas de \u00c1rvores Geradoras em Grafos. PhD thesis, PESC\/COPPE, Universidade Federal do Rio de Janeiro (in Portuguese)"},{"key":"116_CR24","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/3-540-68530-8_37","volume":"1461","author":"S Solis-Oba","year":"1998","unstructured":"Solis-Oba S (1998) 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Lect Notes Comput Sci 1461: 441\u2013452","journal-title":"Lect Notes Comput Sci"},{"key":"116_CR25","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"R Wong","year":"1984","unstructured":"Wong R (1984) A dual ascent approach for Steiner tree problems on a directed graph. Math Prog 28: 271\u2013287","journal-title":"Math Prog"}],"container-title":["Computational Management Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-009-0116-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10287-009-0116-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-009-0116-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T12:12:48Z","timestamp":1559131968000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10287-009-0116-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,7]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["116"],"URL":"https:\/\/doi.org\/10.1007\/s10287-009-0116-5","relation":{},"ISSN":["1619-697X","1619-6988"],"issn-type":[{"value":"1619-697X","type":"print"},{"value":"1619-6988","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,7]]}}}