Abstract
The maximum leaf spanning tree problem consists in finding a spanning tree of a graph that maximizes the number of leaves that the tree has. This problem has been found to be NP-hard for general graphs. It has several relevant applications in the context of telecommunication networks. In this paper, we tackle this problem by proposing the use of a parallel algorithm based on the strategic oscillation methodology. In particular, we propose two different parallel approaches and we compare our best variant with previous algorithms of the state of the art. The proposed approach outperforms previous ones in the state of the art, which is also confirmed by the use of statistical tests.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.
Eduardo García Pardo
Associate Professor
Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.