𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Floats, Integers, and Single Source Shortest Paths

✍ Scribed by Mikkel Thorup

Book ID
102573621
Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
105 KB
Volume
35
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

Floats are ugly, but to everyone but theoretical computer scientists, they are the real thing. A linear time algorithm is presented for the undirected single-source shortest paths problem with nonnegative floating point weights.

πŸ“œ SIMILAR VOLUMES

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

Time–Work Tradeoffs of the Single-Source
Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
✍ Hanmao Shi; Thomas H Spencer πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 111 KB

We give parallel algorithms that solve the single-source shortest paths problem Ε½ . on a weighted, undirected graph with n vertices and m edges in O t lg n time and Ε½Ε½ 3 2 . Ε½ . . Ε½ . Ε½ Ε½ 3 3 O n rt lg n lg nrt q m lg n work, or in O t lg n time and O n rt q . . mnrt lg n work for any t in the range