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 operations in Õ(n2)1 amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic and uses simple data structures.
A new approach to dynamic all pairs shortest paths / Demetrescu, Camil; Giuseppe F., Italiano. - STAMPA. - (2003), pp. 159-166. (Intervento presentato al convegno 35th Annual ACM Symposium on Theory of Computing tenutosi a San Diego; United States) [10.1145/780542.780567].
A new approach to dynamic all pairs shortest paths
DEMETRESCU, Camil;
2003
Abstract
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 operations in Õ(n2)1 amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic and uses simple data structures.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.