Viene proposto un algoritmo distribuito per determinare un insieme di indipendenza massimale per un grafo non diretto. Tale algoritmo è determinato da da un algoritmo centralizzato basato su sequenze di reti neurali di Hopfield. Faremo riferimento al modello sincronizzato del calcolo distribuito nel qualce la topogia è descritta da un grafo. Daremo un limite superiore al numero di messaggi inviati durante la computazione. Per testare l'algoritmo, abbiamo sperimentalmente comparato l'algoritmo con un'euristica probabilistica derivata dal modello di ottimizzazione chiamato 'Ant colony' e con l'algoritmo greedy standard.

A Distributed Algorithm for Max Independent Set Problem Based on Hopfield Networks

POSENATO, Roberto
2002-01-01

Abstract

Viene proposto un algoritmo distribuito per determinare un insieme di indipendenza massimale per un grafo non diretto. Tale algoritmo è determinato da da un algoritmo centralizzato basato su sequenze di reti neurali di Hopfield. Faremo riferimento al modello sincronizzato del calcolo distribuito nel qualce la topogia è descritta da un grafo. Daremo un limite superiore al numero di messaggi inviati durante la computazione. Per testare l'algoritmo, abbiamo sperimentalmente comparato l'algoritmo con un'euristica probabilistica derivata dal modello di ottimizzazione chiamato 'Ant colony' e con l'algoritmo greedy standard.
2002
9783540442653
Max independent set; hopfield networks; asynchronous distributed algorithms
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11562/109
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact