# Solving maximum independent set by asynchronous distributed hopfield-type neural networks

Giuliano Grossi; Massimo Marchi; Roberto Posenato

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 2, page 371-388
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGrossi, Giuliano, Marchi, Massimo, and Posenato, Roberto. "Solving maximum independent set by asynchronous distributed hopfield-type neural networks." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 371-388. <http://eudml.org/doc/249731>.

@article{Grossi2006,

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.
},

author = {Grossi, Giuliano, Marchi, Massimo, Posenato, Roberto},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Max independent set; hopfield networks; asynchronous
distributed algorithms.; max independent set; Hopfield networks; asynchronous distributed algorithms},

language = {eng},

month = {7},

number = {2},

pages = {371-388},

publisher = {EDP Sciences},

title = {Solving maximum independent set by asynchronous distributed hopfield-type neural networks},

url = {http://eudml.org/doc/249731},

volume = {40},

year = {2006},

}

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

DA - 2006/7//

PB - EDP Sciences

VL - 40

IS - 2

SP - 371

EP - 388

AB -
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.

LA - eng

KW - Max independent set; hopfield networks; asynchronous
distributed algorithms.; max independent set; Hopfield networks; asynchronous distributed algorithms

UR - http://eudml.org/doc/249731

ER -

## References

top- T. Bäck and S. Khuri, An evolutionary heuristic for the maximum independent set problem, in Proc. First IEEE Conf. Evolutionary Computation, IEEE World Congress on Computational Intelligence, edited by Z. Michalewicz, J.D. Schaffer, H.-P. Schwefel, D.B. Fogel and H. Kitano, Orlando FL, June 27–29. IEEE Press, Piscataway NJ 2 (1994) 531–535.
- S. Basagni, Finding a maximal weighted independent set in wireless networks. Telecommunication Systems, Special Issue on Mobile Computing and Wireless Networks18 (2001) 155–168. Zbl1020.68005
- R. Battiti and M. Protasi, Reactive local search for the maximum clique problem. Algorithmica29 (2001) 610–637. Zbl0985.68016
- A. Bertoni, P. Campadelli and G. Grossi, A neural algorithm for the maximum clique problem: Analysis, experiments and circuit implementation. Algoritmica33 (2002) 71–88. Zbl0994.68002
- I.M. Bomze, M. Budinich, M. Pelillo and C. Rossi, Annealed replication: A new heuristic for the maximum clique problem. Discrete Appl. Math.121 (2000) 27–49. Zbl1019.90032
- M. Dorigo, G. Di Caro and L.M. Gambardella, Ant algorithms for discrete optimization. Artificial Life5 (1996) 137–172.
- U. Feige, S. Goldwasser, S. Safra, L. Lovàsz and M. Szegedy, Approximating clique is almost NP-complete, in Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science (1991) 2–12.
- T.A. Feo, M.G.C. Resende and S.H. Smith, Greedy randomized adaptive search procedure for maximum independent set. Oper. Res.41 (1993). Zbl0815.90121
- M. Gerla and J.T.-C. Tsai, Multicluster, mobile, multimedia radio network. Wireless Networks1 (1995) 255–265.
- W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks, in Workshop on Advances in Parallel and Distributed Computational Models (2003).
- G. Grossi and R. Posenato, A distributed algorithm for max independent set problem based on Hopfield networks, in Neural Nets: 13th Italian Workshop on Neural Nets (WIRN 2002), edited by M. Marinaro and R. Tagliaferri. Springer-Verlag. Lect. Notes Comput. Sci.2486 (2002) 64–74. Zbl1028.68592
- M.M. Halldórsson and J. Radhakrishnan, Greedy is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica18 (1997) 145–163. Zbl0866.68077
- J. Håstad, Clique is hard to approximate within n1 - ε, in Proc. of the 37rd Annual IEEE Symposium on the Foundations of Computer Science (1996) 627–636.
- J.J. Hopfield, Neural networks and physical systems with emergent collective computational abilities, in Proceedings of the National Academy of Sciences of the United States of America79 (1982) 2554–2558.
- L. Ji-Cherng and T.C. Huang, An efficient fault-containing self-stabilizing algorithm for finding a maximal independent set. IEEE Transactions on Parallel and Distributed Systems14 (2003) 742–754.
- D.S. Johnson and M.A. Trick, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society (1996).
- R.M. Karp, Reducibility among Combinatorial Problems. Complexity of Computer Computations. Plenum Press, New York (1972) 85–103.
- G. Leguizam'on, Z. Michalewicz and M. Sch"utz, An ant system for the maximum independent set problem, in Proceedings of VII Argentine Congress of Computer Science (CACIC 2001) (2001).
- S.Z. Li, Improving convergence and solution quality of Hopfield-type neural networks with augmented Lagrange multipliers. IEEE Trans. Neural Networks7 (1996) 1507–1516.
- E. Marchiori, A simple heuristic based genetic algorithm for the maximum clique problem, in Proc. ACM Symp. Appl. Comput (1998) 366–373.
- C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.