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 / G. Grossi, M. Marchi, R. Posenato. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - 40:2(2006), pp. 371-388.
Solving maximum independent set by asynchronous distributed hopfield-type neural networks
G. Grossi;
2006
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.