𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Semidynamic Algorithms for Maintaining Single-Source Shortest Path Trees

✍ Scribed by D. Frigioni; A. Marchetti-Spaccamela; U. Nanni

Publisher
Springer
Year
1998
Tongue
English
Weight
366 KB
Volume
22
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

A Randomized Parallel Algorithm for Sing
A Randomized Parallel Algorithm for Single-Source Shortest Paths
✍ Philip N Klein; Sairam Subramanian πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 179 KB

We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of approximate shortest-path subproblems. Our algorithm for the approximate shortest-path problem is ba