Seminari del Dipartimento di Matematica

Seminario del 2007

Elisabetta Scoppola - Università Roma Tre

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

nell'ambito della serie: SEMINARI DI FISICA MATEMATICA

fisica matematica

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.