Geodesic
Solving maximum independent set by asynchronous distributed hopfield-type neural networks
Grossi, Giuliano ; Marchi, Massimo ; Posenato, Roberto1
1 Dipartimento di Informatica, Università degli Studi di Verona, strada le grazie 15, 37134 Verona, Italy.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 371-388

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita:2006012
Classification : 68W15, 90C59, 05C69
Keywords: max independent set, hopfield networks, asynchronous distributed algorithms

Grossi, Giuliano  ; Marchi, Massimo  ; Posenato, Roberto 1

1 Dipartimento di Informatica, Università degli Studi di Verona, strada le grazie 15, 37134 Verona, Italy. 
@article{ITA_2006__40_2_371_0,
     author = {Grossi, Giuliano and Marchi, Massimo and Posenato, Roberto},
     title = {Solving maximum independent set by asynchronous distributed hopfield-type neural networks},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {371--388},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {2},
     year = {2006},
     doi = {10.1051/ita:2006012},
     mrnumber = {2252645},
     zbl = {1112.68119},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2006012/}
}
TY  - JOUR
AU  - Grossi, Giuliano
AU  - Marchi, Massimo
AU  - Posenato, Roberto
TI  - Solving maximum independent set by asynchronous distributed hopfield-type neural networks
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 371
EP  - 388
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2006012/
DO  - 10.1051/ita:2006012
LA  - en
ID  - ITA_2006__40_2_371_0
ER  - 
%0 Journal Article
%A Grossi, Giuliano
%A Marchi, Massimo
%A Posenato, Roberto
%T Solving maximum independent set by asynchronous distributed hopfield-type neural networks
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 371-388
%V 40
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2006012/
%R 10.1051/ita:2006012
%G en
%F ITA_2006__40_2_371_0
Grossi, Giuliano; Marchi, Massimo; Posenato, Roberto. Solving maximum independent set by asynchronous distributed hopfield-type neural networks. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 371-388. doi: 10.1051/ita:2006012

Cité par Sources :