𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved Algorithms for Dynamic Shortest Paths

✍ Scribed by H. N. Djidjev; G. E. Pantziou; C. D. Zaroliagis

Publisher
Springer
Year
2000
Tongue
English
Weight
128 KB
Volume
28
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Fully Dynamic Algorithms for Maintaining
Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
✍ Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 213 KB

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal quer

Improved shortest path algorithms for ne
Improved shortest path algorithms for nearly acyclic graphs
✍ Shane Saunders; Tadao Takaoka πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 202 KB

Dijkstra's algorithm solves the single-source shortest path problem on any directed graph in O(m + n log n) time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices and m is the number of edges in the graph. If the graph is nearly acyclic, other algorit

A fully dynamic algorithm for distribute
A fully dynamic algorithm for distributed shortest paths
✍ Serafino Cicerone; Gabriele Di Stefano; Daniele Frigioni; Umberto Nanni πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 297 KB

We propose a fully dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If is the number of pairs of nodes changing the distance after a single edge modiΓΏcation (insert, delete, weight decrease, or weight increase) then the messa