Algoritmi di approssimazione dei cammini minimi nei grafi incerti

Il problema di identificare i cammini minimi su grafi è una primitiva fondamentale con innumerevoli applicazioni. I grafi incerti (uncertain graphs) sono una generalizzazione dei grafi pesati, nei quali ogni arco è associato ad una propria probabilità di esistenza. La necessità di tenere conto dell’incertezza legata all’esistenza degli archi nei grafi incerti rende il problema di calcolare i cammini minimi particolarmente difficile da risolvere. Questa tesi presenta algoritmi sviluppati recentemente per calcolare in modo efficiente i percorsi più brevi tra i nodi dei grafi incerti, e propone una valutazione sperimentalmente delle relative prestazioni su grafi provenienti da applicazioni reali.