Chan (Geometrically Weighted) (APSP on Geometrically Weighted Graphs All-Pairs Shortest Paths (APSP))

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(n^{2.{84}4})$

Space Complexity

$O(l n^{2})$ words

(Derived: Compute and store $2l$ $V \times V$ matrices)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2009

Reference

http://tmc.web.engr.illinois.edu/moreapsp.pdf