A distributed algorithm to find a maximal independent set of an undirected graph is proposed. It is borrowed by a centralized one and it is based on a sequence of Hopfield neural networks. We refer to the synchronous model of distributed computation in which the topology is described by the graph. We give an upper bound on the number of messages sent during the entire process of computation. To test the algorithm we experimentally compare it with a probabilistic heuristic derived by Ant Colony Optimization technique and with the standard greedy algorithm.

A distributed algorithm for max independent set problem based on Hopfield networks / G. Grossi, R. Posenato (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). - In: Neural Nets / [a cura di] M. Marinaro, R. Tagliaferri. - [s.l] : Springer Verlag, 2002. - ISBN 978-3-540-44265-3. - pp. 64-74 (( Intervento presentato al 13. convegno WIRN tenutosi a Vietri sul Mare nel 2002 [10.1007/3-540-45808-5_6].

A distributed algorithm for max independent set problem based on Hopfield networks

G. Grossi;
2002

Abstract

A distributed algorithm to find a maximal independent set of an undirected graph is proposed. It is borrowed by a centralized one and it is based on a sequence of Hopfield neural networks. We refer to the synchronous model of distributed computation in which the topology is described by the graph. We give an upper bound on the number of messages sent during the entire process of computation. To test the algorithm we experimentally compare it with a probabilistic heuristic derived by Ant Colony Optimization technique and with the standard greedy algorithm.
Hopfield networks; Max independent set; Synchronous distributed algorithms
Settore INF/01 - Informatica
'Univ. of Milano, Dip. di Scienze dell'Informazione'
et al.
Int. Inst. Adv. Sci. Stud. (IIASS) "E.R. Caianiello"
Societa Italiana Reti Neuroniche (SIREN)
Univ. of Salerno, Dip. di Fisica "E.R. Caianiello"
Univ. of Salerno, Dip. di Matematica ed Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
3-540-45808-5_6.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 171.63 kB
Formato Adobe PDF
171.63 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/937916
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact