A spanning caterpillar in a graph is a tree composed by a path such that all vertices not in the path are leaves. In the Minimum Spanning Caterpillar Problem (MSCP) each edge has two costs: a path cost when it belongs to the path and a connection cost when it is incident to a leaf. The goal is to find a spanning caterpillar minimizing the sum of all path and connection costs. In this paper we formulate the as a minimum Steiner arborescence problem. This reduction is the basis for the development of an efficient branch-and-cut algorithm for the MSCP. We als developed a GRASP heuristic to generate primal bounds. Experiments carried out on instances adapted from TSPLIB 2.1 revealed that the exact algorithm is capable to solve to optimality instances with up to 300 vertices in reasonable time. They also showed that our heuristic yields very high quality solutions. © 2009 Elsevier B.V. All rights reserved.35C8388Adhar, G.S., Optimum interval routing in k-caterpillars and maximal outer planar networks (2003) Applied Informatics, pp. 692-696Baldacci, R., Dell'Amico, M., Salazar, J.J., The Capacitated m-Ring Star Problem (2007) Operations Research, 55, pp. 1147-1162Bauer, P., The circuit polytope: Facets (1997) Oper. Research, 22, pp. 110-145Fischetti, M., Salazar, J.J., Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem (1997) Operations Research, 45, pp. 378-394Gouveia, L., Simonetti, L., Uchoa, E., Modelling the hop-constrained minimum spanning tree problem over a layered graph (2007) International Network Optimization ConferenceHoshino, E.A., de Souza, C.C., Column Generation Algorithms for the Capacitated m-Ring-Star Problem, COCOON (2008) Lecture Notes in Computer Science, 5092, pp. 631-641. , Springer, DalianLabbé, M., Laporte, G., Martín, I.R., González, J.S., The Ring Star Problem: Polyhedral Analysis and Exact Algorithm (2004) Networks, 43, pp. 177-189Lee, Y., Chiu, S.Y., Sanchez, J., A branch and cut algorithm for the Steiner ring star problem (1998) Int. J. Manag. Sci., 4, pp. 21-34Proskurowski, A., Telle, J.A., Classes of graphs with restricted interval models (1999) Disc. Math. and Theoretical Computer Science, 3-4, pp. 167-176Reinelt, G., A traveling salesman problem library (1991) ORSA J Comp, 3, pp. 376-384Resende, M.G.C., Ribeiro, C.C., (2005) GRASP with path-relinking: Recent advances and applications, Metaheuristics: Progress as real problem solvers, pp. 29-63. , Ibaraki T., Nonobe K., and Yagiura M. (Eds), SpringerTan, J., Zhang, L., Approximation Algorithms for the Consecutive Ones Submatrix Problem on Sparse Matrices (2004) Lecture Notes in Computer Science, 3341, pp. 835-846Xu, J., Chiu, S.Y., Glover, F., Optimizing a ring-based private line telecommunication network using tabu search (1999) Manag. Sci., 45, pp. 330-345