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...

Descripció completa

Dades bibliogràfiques
Autor principal: Bernstein, Aaron
Altres autors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Idioma:en_US
Publicat: 2010
Matèries:
shortest paths
graph algorithms
dynamic algorithms
approximation algorithms
Accés en línia:http://hdl.handle.net/1721.1/58901

Internet

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

Ítems similars