Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time

Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time

For any fixed 1 > [epsilon] > 0 we present a fully dynamic algorithm for maintaining (2 + [epsilon])-approximate all-pairs shortest paths in undirected graphs with positive edge weights. We use a randomized (Las Vegas) update algorithm (but a deterministic query procedure), so the time given i...

Full description

Bibliographic Details
Main Author: Bernstein, Aaron
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: 2010
Subjects:
shortest paths
graph algorithms
dynamic algorithms
approximation algorithms
Online Access:http://hdl.handle.net/1721.1/58901

Internet

http://hdl.handle.net/1721.1/58901

Similar Items