a.a. 2024/25

Responsabile didattico: Alberto Policriti

Periodo: secondo semestre

Durata: 28 ore

Programma: In teoria dei grafi la ricerca di algoritmi per risolvere il problema dell’isomorfismo tra grafi rappresenta una delle più interessanti sfide ancora aperte. Il test di Weisfeiler-Lehman è, essenzialmente, una collezione parametrica di algoritmi che risale al 1968 e che ha ricevuto e sta ricevendo una notevole attenzione da parte della comunità scientifica. Anche nei casi in cui il test non è completo (possono esserci grafi non isomorfi che passano il test per un fissato valore del parametro) il test di Weisfeiler Leman con valori del parametro relativamente bassi, si è dimostrato molto utile ed interessante. Ha trovato applicazioni allo studio delle reti neurali, in chimica computazionale e nel disegno di circuiti. Il test è inoltre molto interessante anche da un punto di vista teorico, con varie caratterizzazioni algebriche e logiche eleganti e naturali.
Dopo una breve introduzione al problema dell'isomorfismo fra grafi e alla sua complessità, nel corso verranno illustrate e discusse le tematiche principali legate al test, sia da un punto di vista teorico che applicativo.

Corsi a.a. 2024/2025