Seminari del Dipartimento di Matematica

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.

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.