Chan (APSP on Dense Directed Graphs with Arbitrary Weights; APSP on Dense Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)): Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

10 April 2023

15 February 2023

  • curprev 11:3811:38, 15 February 2023‎ Admin talk contribs‎ 427 bytes +427‎ Created page with "== Time Complexity == $O(V^{3} \log^{3} \log V / \log^{2} V)$ == Space Complexity == $O(V^{2})$ words (Derived: Dividing $A$ and $B$ into $V \times q$ and $q \times V$ matrices, in total using $O(V^2)$ space ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == http://tmc.web.engr.illinois.edu/moreapsp.pdf"
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Chan_(APSP_on_Dense_Directed_Graphs_with_Arbitrary_Weights;_APSP_on_Dense_Undirected_Graphs_with_Arbitrary_Weights_All-Pairs_Shortest_Paths_(APSP))"