Graph Partitioning via Recurrent Multivalued Neural Networks

 

Abstract

In this work, the well-known Graph Partitioning (GP) problem for undirected weighted graphs has been studied from two points of view: maximizing (MaxCut) or minimizing (MinCut) the cost of the cut induced in the graph by the partition. An unified model, based on a neural technique for optimization problems, has been applied to these two concrete problems. A detailed description of the model is presented, and the technique to minimize an energy function, that measures the goodness of solutions, is fully described. Some techniques to escape from local optima are presented as well. It has proved to be a very competitive and efficient algorithm, in terms of quality of solutions and computational time, when compared to the state-of-the-art methods. Some simulation results are presented in this paper, to show the comparative efficiency of the methods.

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Citation

Please, cite this work as:

[CL05] E. M. Casermeiro and D. López-Rodríguez. “Graph Partitioning via Recurrent Multivalued Neural Networks”. In: Computational Intelligence and Bioinspired Systems, 8th International Work-Conference on Artificial Neural Networks, IWANN 2005, Vilanova i la Geltrú, Barcelona, Spain, June 8-10, 2005, Proceedings. Ed. by J. Cabestany, A. Prieto and F. S. Hernández. Vol. 3512. Lecture Notes in Computer Science. Vilanova i la Geltru: Springer, 2005, pp. 1149-1156. DOI: 10.1007/11494669_141. URL: https://doi.org/10.1007/11494669_141.

BibTeX

@InProceedings{Casermeiro2005a,
     author = {Enrique Mérida Casermeiro and Domingo López-Rodríguez},
     booktitle = {Computational Intelligence and Bioinspired Systems, 8th International Work-Conference on Artificial Neural Networks, {IWANN} 2005, Vilanova i la Geltrú, Barcelona, Spain, June 8-10, 2005, Proceedings},
     title = {Graph Partitioning via Recurrent Multivalued Neural Networks},
     year = {2005},
     address = {Vilanova i la Geltru},
     editor = {Joan Cabestany and Alberto Prieto and Francisco Sandoval Hernández},
     pages = {1149–1156},
     publisher = {Springer},
     series = {Lecture Notes in Computer Science},
     volume = {3512},
     abstract = {In this work, the well-known Graph Partitioning (GP) problem for undirected weighted graphs has been studied from two points of view: maximizing (MaxCut) or minimizing (MinCut) the cost of the cut induced in the graph by the partition. An unified model, based on a neural technique for optimization problems, has been applied to these two concrete problems. A detailed description of the model is presented, and the technique to minimize an energy function, that measures the goodness of solutions, is fully described. Some techniques to escape from local optima are presented as well. It has proved to be a very competitive and efficient algorithm, in terms of quality of solutions and computational time, when compared to the state-of-the-art methods. Some simulation results are presented in this paper, to show the comparative efficiency of the methods. © Springer-Verlag Berlin Heidelberg 2005.},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/conf/iwann/CasermeiroL05.bib},
     document_type = {Conference Paper},
     doi = {10.1007/11494669_141},
     journal = {Lecture Notes in Computer Science},
     keywords = {Algorithms; Computational methods; Computer simulation; Graph theory; Optimization; Problem solving, Computational time; Graph partitioning; Optimization problems, Neural networks},
     source = {Scopus},
     timestamp = {Tue, 14 May 2019 10:00:51 +0200},
     url = {https://doi.org/10.1007/11494669_141},
}