Reformulations And Solution Algorithms For The Maximum Leaf Spanning Tree Problem

dc.creatorLucena A.
dc.creatorMaculan N.
dc.creatorSimonetti L.
dc.date2010
dc.date2015-06-26T12:41:23Z
dc.date2015-11-26T15:29:06Z
dc.date2015-06-26T12:41:23Z
dc.date2015-11-26T15:29:06Z
dc.date.accessioned2018-03-28T22:37:50Z
dc.date.available2018-03-28T22:37:50Z
dc.identifier
dc.identifierComputational Management Science. , v. 7, n. 3, p. 289 - 311, 2010.
dc.identifier1619697X
dc.identifier10.1007/s10287-009-0116-5
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-77954087471&partnerID=40&md5=c1f35f6bc13f03ab19635e045fac04ff
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/91455
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/91455
dc.identifier2-s2.0-77954087471
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1261759
dc.descriptionGiven a graph G = (V, E), the maximum leaf spanning tree problem (MLSTP) is to find a spanning tree of G with as many leaves as possible. The problem is easy to solve when G is complete. However, for the general case, when the graph is sparse, it is proven to be NP-hard. In this paper, two reformulations are proposed for the problem. The first one is a reinforced directed graph version of a formulation found in the literature. The second recasts the problem as a Steiner arborescence problem over an associated directed graph. Branch-and-Cut algorithms are implemented for these two reformulations. Additionally, we also implemented an improved version of a MLSTP Branch-and-Bound algorithm, suggested in the literature. All of these algorithms benefit from pre-processing tests and a heuristic suggested in this paper. Computational comparisons between the three algorithms indicate that the one associated with the first reformulation is the overall best. It was shown to be faster than the other two algorithms and is capable of solving much larger MLSTP instances than previously attempted in the literature. © 2010 Springer-Verlag.
dc.description7
dc.description3
dc.description289
dc.description311
dc.descriptionAneja, Y.P., An integer linear programming approach to the Steiner problem in graphs (1980) Networks, 10, pp. 167-178
dc.descriptionChopra, S., Gorres, E., Rao, M.R., Solving Steiner tree problem on a graph using branch and cut (1992) ORSA J Comput, 4 (3), pp. 320-335
dc.descriptionEdmonds, J., Matroids and the greedy algorithm (1971) Math Prog, 1, pp. 127-136
dc.descriptionFernandes, M.L., Gouveia, L., Minimal spanning trees with a constraint on the number of leaves (1998) Eur J Oper Res, 104, pp. 250-261
dc.descriptionFujie, T., An exact algorithm for the maximum-leaf spanning tree problem (2003) Comput Oper Res, 30, pp. 1931-1944
dc.descriptionFujie, T., The maximum-leaf spanning tree problem: Formulations and facets (2004) Networks, 43 (4), pp. 212-223
dc.descriptionGalbiati, G., Maffioli, F., Morzenti, A., A short note on the approximability of the maximum leaves spanning tree problem (1994) Info Proc Lett, 52, pp. 45-49
dc.descriptionGarey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , New York: W. H. Freeman
dc.descriptionGuha, S., Khuller, S., Approximation algorithms for connected dominating sets (1998) Algorithmica, 20 (4), pp. 374-387
dc.descriptionKoch, T., Martin, A., Solving Steiner tree problems in graphs to optimality (1998) Networks, 33, pp. 207-232
dc.descriptionLu, H., Ravi, R., Approximating maximum leaf spanning trees in almost linear time (1998) J Algo, 29, pp. 132-141
dc.descriptionPoggi de Aragão, M., Uchoa, E., Werneck, R., Dual heuristics on the exact solution of large Steiner problems (2001) Electron Notes Discret Math, 7, pp. 150-153
dc.descriptionPolzin, T., Daneshmand, S.V., Improved algorithms for the Steiner problem in networks (2001) Discret Appl Math, 112 (1-3), pp. 263-300
dc.descriptionResende, M.G.C., Pardalos, P.M., (2006) Handbook of Optimization in Telecommunications, , New York: Springer
dc.descriptionSolis-Oba, S., 2-approximation algorithm for finding a spanning tree with maximum number of leaves (1998) Lect Notes Comput Sci, 1461, pp. 441-452
dc.descriptionWong, R., A dual ascent approach for Steiner tree problems on a directed graph (1984) Math Prog, 28, pp. 271-287
dc.languageen
dc.publisher
dc.relationComputational Management Science
dc.rightsfechado
dc.sourceScopus
dc.titleReformulations And Solution Algorithms For The Maximum Leaf Spanning Tree Problem
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución