A Multivalued Neural Network for the Degree-Constrained Minimum Spanning Tree Problem

 

Abstract

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.

Citation

Please, cite this work as:

[LMO07] D. López-Rodríguez, E. Mérida-Casermeiro, and J. M. Ortiz-de-Lazcano-Lobato. “A multivalued neural network for the degree-constrained minimum spanning tree problem”. In: CAEPIA-TTIA 2007: actas. 2007, pp. 269-278.

BibTeX

@inproceedings{domingo2007multivalued,
     title={A multivalued neural network for the degree-constrained minimum spanning tree problem},
     author={López-Rodríguez, Domingo and Mérida-Casermeiro, Enrique and Ortiz-de-Lazcano-Lobato, Juan Miguel},
     booktitle={CAEPIA-TTIA 2007: actas},
     pages={269–278},
     year={2007}
}