Graph Partitioning via Recurrent Multivalued Neural Networks

Combinatorial optimization
Neural networks
Authors

Enrique Mérida Casermeiro

Domingo López-Rodríguez

Published

1 January 2005

Publication details

International Work-Conference on Artificial Neural Networks (IWANN) 2005, Lecture Notes in Computer Science, (3512), pp. 1149–1156

Links

DOI

 

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.

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.

@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},
}

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

Graph Partitioning via Recurrent Multivalued Neural Networks

Cites

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

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

  1. Mohd. Samar Ansari (2016). A Voltage-Mode Nonlinear-Synapse Neural Circuit for Bi-partitioning of Graphs. DOI
  2. Domingo López-Rodríguez, Enrique Mérida-Casermeiro (2009). Shortest Common Superstring Problem with Discrete Neural Networks. Lecture notes in computer science DOI
  3. Enrique Mérida-Casermeiro, Domingo López-Rodríguez, Juan Miguel Ortiz-de-Lazcano-Lobato (2009). An Approach to Artificial Concept Learning Based on Human Concept Learning by Using Artificial Neural Networks. IGI Global eBooks DOI
  4. Enrique Mérida-Casermeiro, Domingo López-Rodríguez, Juan Miguel Ortiz-de-Lazcano-Lobato (2009). MREM, Discrete Recurrent Network for Optimization. IGI Global eBooks DOI
  5. Rafael Marcos Luque‐Baena, Domingo López-Rodríguez, Enrique Mérida-Casermeiro, et al. (2008). Video Object Segmentation with Multivalued Neural Networks. DOI
  6. Enrique Mérida-Casermeiro, Domingo López-Rodríguez (2008). Drawing Graphs in Parallel Lines with Artificial Neural Networks. DOI
  7. Domingo López-Rodríguez, Enrique Mérida-Casermeiro, Juan Miguel Ortiz-de-Lazcano-Lobato, et al. (2007). K-Pages Graph Drawing with Multivalued Neural Networks. Lecture notes in computer science DOI
  8. Domingo López-Rodríguez, Enrique Mérida-Casermeiro, Juan Miguel Ortiz-de-Lazcano-Lobato, et al. (2007). Two Pages Graph Layout Via Recurrent Multivalued Neural Networks. Lecture notes in computer science DOI
  9. Domingo López-Rodríguez, Enrique Mérida-Casermeiro, Gloria Galán-Marín, et al. (2007). Stochastic Functional Annealing as Optimization Technique: Application to the Traveling Salesman Problem with Recurrent Networks. Lecture notes in computer science DOI
  10. Domingo López-Rodríguez, Enrique Mérida-Casermeiro, Juan Miguel Ortiz-de-Lazcano-Lobato (2006). Stochastic multivalued network for optimization: application to the graph Maxcut problem. Computational intelligence
  11. Enrique Mérida-Casermeiro, Domingo López-Rodríguez, Juan Miguel Ortiz-de-Lazcano-Lobato (2006). Enhanced MaxCut Clustering with Multivalued Neural Networks and Functional Annealing. The European Symposium on Artificial Neural Networks