Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
In molti problemi di ottimizzazione combinatorica, come la colorazione di un grafo, si osserva un fenomeno che rende il grafo sempre colorabile con un numero limitato di colori al di sopra di una certa soglia di variabilita' dei parametri del problema, mai colorabile al di sotto di una certa soglia. Analogo fenomeno si osserva per il problema della soddisfacibilita' di formule booleane.

In questo seminario presentero' un calcolo analitico della soglia di colorabilita' nel caso di un grafo random quando il numero di vertici adiacenti ad uno dato segue una distribuzione di Poisson. Il calcolo utilizza sia tecniche di meccanica statistica, sia l'analisi delle equazioni per la propagazione dei belief che quelle piu' recenti per la propagazione dei survey.