We propose a heuristic for solving the maximum independent set problem for a set of processors in a network with arbitrary topology. We assume an asynchronous model of computation and we use modified Hopfield neural networks to find high quality solutions. We analyze the algorithm in terms of the number of rounds necessary to find admissible solutions both in the worst case (theoretical analysis) and in the average case (experimental Analysis). We show that our heuristic is better than the greedy one at 1% significance level.

Solving Maximum Independent Set by Asynchronous Distributed Hopfield-Type Neural Networks

POSENATO, Roberto
2006-01-01

Abstract

We propose a heuristic for solving the maximum independent set problem for a set of processors in a network with arbitrary topology. We assume an asynchronous model of computation and we use modified Hopfield neural networks to find high quality solutions. We analyze the algorithm in terms of the number of rounds necessary to find admissible solutions both in the worst case (theoretical analysis) and in the average case (experimental Analysis). We show that our heuristic is better than the greedy one at 1% significance level.
maximum independent set; approximation algorithm
File in questo prodotto:
File Dimensione Formato  
articoloPubblicoDefinitivoITA_2006__40_2_371_0.pdf

accesso aperto

Descrizione: Articolo definitivo
Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 264.65 kB
Formato Adobe PDF
264.65 kB Adobe PDF Visualizza/Apri

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/302215
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact