Resumen
Given an undirected and connected graph, the maximum leaf spanning tree problem consists in finding a spanning tree with as many leaves as possible. This NP -hard problem has practical applications in telecommunication networks, circuit layouts, and other graph-theoretic problems. An interesting application appears in the context of broadcasting in telecommunication networks, where it is interesting to reduce the number of broadcasting computers in the network. These components are relatively expensive and therefore its is desirable to deploy as few of them as possible in the network. This optimization problem is equivalent to maximize the number of non-broadcasting computers. We present a strategic oscillation approach for solving the maximum leaf spanning tree problem. The results obtained by the proposed algorithm are compared with the best previous algorithm found in the literature, showing the superiority of our proposal.
Jesús Sánchez-Oro
Profesor Titular de Universidad
Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.
Abraham Duarte
Catedrático de Universidad
Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.