Solving maximum independent set by asynchronous distributed hopfield-type neural networks
Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy; email@example.com
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