Questo sito utilizza solo cookie tecnici per il corretto funzionamento delle pagine web e per il miglioramento dei servizi.
Se vuoi saperne di più o negare il consenso consulta l'informativa sulla privacy.
Proseguendo la navigazione del sito acconsenti all'uso dei cookie.
Se vuoi saperne di più o negare il consenso consulta l'informativa sulla privacy.
Proseguendo la navigazione del sito acconsenti all'uso dei cookie.
Seminario del 2007
2007
16 aprile
Elisabetta Scoppola - Università Roma Tre
nell'ambito della serie: SEMINARI DI FISICA MATEMATICA
Seminario di 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.