Seminario di fisica matematica
ore
17:00
presso Seminario I
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.