APSP on Dense Undirected Graphs with Positive Integer Weights: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 18: | Line 18: | ||
== Table of Algorithms == | == Table of Algorithms == | ||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
== Time Complexity | ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | ||
|- | |||
| [[Thorup (APSP on Dense Undirected Graphs with Positive Integer Weights; APSP on Sparse Undirected Graphs with Positive Integer Weights All-Pairs Shortest Paths (APSP))|Thorup]] || 1999 || $O(EV)$ || $O(EV)$ || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf Space] | |||
|- | |||
|} | |||
== Time Complexity Graph == | |||
[[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Positive Integer Weights - Time.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Positive Integer Weights - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Positive Integer Weights - Space.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Positive Integer Weights - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Positive Integer Weights - Pareto Frontier.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Positive Integer Weights - Pareto Frontier.png|1000px]] | ||
Revision as of 14:04, 15 February 2023
Description
In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has positive integer weights.
Related Problems
Generalizations: APSP
Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Sparse Directed Graphs with Arbitrary Weights, APSP on Sparse Undirected Graphs with Positive Integer Weights, APSP on Sparse Undirected Graphs with Arbitrary Weights, APSP on Dense Directed Unweighted Graphs, APSP on Dense Undirected Unweighted Graphs, APSP on Sparse Directed Unweighted Graphs, APSP on Sparse Undirected Unweighted Graphs, (5/3)-approximate ap-shortest paths
Parameters
n: number of vertices
m: number of edges
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Thorup | 1999 | $O(EV)$ | $O(EV)$ | Exact | Deterministic | Time & Space |
Time Complexity Graph
_-_APSP_on_Dense_Undirected_Graphs_with_Positive_Integer_Weights_-_Time.png)
Space Complexity Graph
_-_APSP_on_Dense_Undirected_Graphs_with_Positive_Integer_Weights_-_Space.png)
Pareto Frontier Improvements Graph
_-_APSP_on_Dense_Undirected_Graphs_with_Positive_Integer_Weights_-_Pareto_Frontier.png)