Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract: We present the first fully dynamic algorithm for maintaining all pairs shortest paths in directed graphs with real-valued edge weights. Given a dynamic directed graph G such that each edge can assume at most S different real values, we show how to support updates deterministically in O(S*n^{2.5}*log^3 n) amortized time and queries in optimal worst-case time. No previous fully dynamic algorithm was known for this problem. In the special case where edge weights can only be increased, we give a randomized algorithm with one-sided error which supports updates faster in O(S*n*log^3 n) amortized time.

Joint work with Camil Demetrescu