Il problema di cammino minimo in reti con semafori

Questa tesi prende in considerazione il problema di cammino minimo in grafi orientati con finestre temporali. Seguendo l'approccio di Ahuja et al. (2002), si dimostra che il problema è risolvibile in tempo polinomiale. Viene presentato un algoritmo di tipo polinomiale per la soluzione del problema, dovuto a Chen & Yang (2000). Viene discussa la complessità computazionale del problema. Viene presentato l'algoritmo A* di Zhao et al. (2008) per il problema di cammino minimo tempo-dipendente e, infine, si propone una nuova applicazione di questo algoritmo al problema con finestre temporali.