Ricerca della massima clique con un algoritmo ispirato al metodo della cavità.

Si discuterà il problema della determinazione del massimo sottografo completo (o massima clique) di un dato grafo. In particolare, ispirandosi al metodo della cavità utilizzato nei vetri di spin, si introdurrà una Monte Carlo Markov Chain (MCMC) con misura invariante concentrata sulle massime cliques. L'algoritmo cosi' introdotto ha ottime prestazioni sui grafi benchmark DIMACS. Verranno infine fatte alcune considerazioni sul tempo di mixing della catena.