Resumen de A multivalued neural network for the degree-constrained minimum spanning tree problem

Domingo López Rodríguez, Enrique Mérida Casermeiro , Juan Miguel Ortiz de Lazcano Lobato

• The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper, a new neural heuristic for the DCMST problem has been developed, making use of the multivalued recurrent model MREM, that has obtained very good results in other combinatorial optimization problems. The computational performance of our approach is compared against the performance of some algorithms from specialized literature. All these approaches are tested using standard problems taken from the literature.