| Issue |
RAIRO-Theor. Inf. Appl.
Volume 40, Number 2, April-June 2006
Alberto Bertoni: Climbing summits
|
|
|---|---|---|
| Page(s) | 371 - 388 | |
| DOI | https://doi.org/10.1051/ita:2006012 | |
| Published online | 20 July 2006 | |
Solving maximum independent set by asynchronous distributed hopfield-type neural networks
1
Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy; grossi@dsi.unimi.it
2
Dipartimento di Informatica, Università degli Studi di
Verona, strada le grazie 15, 37134 Verona, Italy.
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.
Mathematics Subject Classification: 68W15 / 90C59 / 05C69
Key words: Max independent set / hopfield networks / asynchronous distributed algorithms.
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.