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 · n2.5 log3 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 log3 n) amortized time.
Fully dynamic all pairs shortest paths with real edge weights / Demetrescu, Camil; G. F., Italiano. - (2001), pp. 260-267. ( 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001) LAS VEGAS, NV OCT 14-17, 2001) [10.1109/sfcs.2001.959900].
Fully dynamic all pairs shortest paths with real edge weights
DEMETRESCU, Camil;
2001
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 · n2.5 log3 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 log3 n) amortized time.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
