Reformulations and solution algorithms for the maximum leaf spanning tree problem

Aneja YP (1980) An integer linear programming approach to the Steiner problem in graphs. Networks 10: 167–178

Balasundaram B, Butenko S (2006) Graph domination, coloring and cliques in telecommunications. In: Handbook of optimization in telecommunications. Springer, New York, pp 865–890

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–54

Chen S, Ljubić I, Raghavan S (2009) The regenerator location problem. Networks (to appear)

Chopra S, Gorres E, Rao MR (1992) Solving Steiner tree problem on a graph using branch and cut. ORSA J Comput 4(3): 320–335

Edmonds J (1971) Matroids and the greedy algorithm. Math Prog 1: 127–136

Fernandes ML, Gouveia L (1998) Minimal spanning trees with a constraint on the number of leaves. Eur J Oper Res 104: 250–261

Fujie T (2003) An exact algorithm for the maximum-leaf spanning tree problem. Comput Oper Res 30: 1931–1944

Fujie T (2004) The maximum-leaf spanning tree problem: formulations and facets. Networks 43(4): 212–223

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–49

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, New York

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)

Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4): 374–387

Koch T, Martin A (1998) Solving Steiner tree problems in graphs to optimality. Networks 33: 207–232

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–542

Lu H, Ravi R (1998) Approximating maximum leaf spanning trees in almost linear time. J Algo 29: 132–141

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–48

Magnanti TL, Wolsey LA (1995) Optimal trees. In: Network models. Handbooks in operations research and management science, vol 7. North Holland, Amsterdam, pp 503–615

Marathe MV, Breu H, Hunt III HB, Ravi SS, Rosenkrantz DJ (1995) Simple heuristics for unit disc graphs. Networks 25

Poggi de Arag⭠M, Uchoa E, Werneck R (2001) Dual heuristics on the exact solution of large Steiner problems. Electron Notes Discret Math 7:150–153

Polzin T, Daneshmand SV (2001) Improved algorithms for the Steiner problem in networks. Discret Appl Math 112(1-3): 263–300

Resende MGC, Pardalos PM (2006) Handbook of optimization in telecommunications. Springer, New York

Simonetti LG (2008) Otimização Combinatória: Problemas de Árvores Geradoras em Grafos. PhD thesis, PESC/COPPE, Universidade Federal do Rio de Janeiro (in Portuguese)

Solis-Oba S (1998) 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Lect Notes Comput Sci 1461: 441–452

Wong R (1984) A dual ascent approach for Steiner tree problems on a directed graph. Math Prog 28: 271–287