A new approach to dynamic all pairs shortest paths.

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operati...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής

Τόπος έκδοσης:	Journal of the ACM 51, 6 (2004).
Κύριος συγγραφέας:	Demetrescu, Camil
Μορφή:	Άρθρο
Γλώσσα:	English
Θέματα:	Data. Data structures. Graphs and networks. Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Computations and discrete structures. Mathematics of computing. Discrete mathematics. Graph theory. Graph algorithms. Algorithms.