Shortest paths and loop-free routing in dynamic networks
Baruch Awerbuch · 1990
In this paper, we survey the existing methods for designing shortest paths routing algorithms for dynamic networks. We compare them based on worst-case communication and message complexity, and suggest new approach that yields a protocol with linear time and polynomial communication.