APSP on Dense Undirected Graphs with Arbitrary Weights: Difference between revisions

Revision as of 14:04, 15 February 2023

In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has arbitrary weights.

Generalizations: APSP

n: number of vertices

m: number of edges

Name	Year	Time	Space	Approximation Factor	Model	Reference
Pettie & Ramachandran	2002	$O(EV \log \alpha(E,V))$		Exact	Deterministic	Time
Chan	2009	$O(V^{3} \log^{3} \log V / \log^{2} V)$	$O(V^{2})$	Exact	Deterministic	Time

@@ Line 18: / Line 18: @@
 == Table of Algorithms ==
-Currently no algorithms in our database for the given problem.
+{| class="wikitable sortable"  style="text-align:center;" width="100%"
-== Time Complexity graph ==
+! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference
+|-
+| [[Pettie & Ramachandran (APSP on Dense Undirected Graphs with Arbitrary Weights; APSP on Sparse Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Pettie & Ramachandran]] || 2002 || $O(EV \log \alpha(E,V))$ ||  || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=545417 Time]
+|-
+| [[Chan (APSP on Dense Directed Graphs with Arbitrary Weights; APSP on Dense Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP))|Chan]] || 2009 || $O(V^{3} \log^{3} \log V / \log^{2} V)$ || $O(V^{2})$ || Exact || Deterministic || [http://tmc.web.engr.illinois.edu/moreapsp.pdf Time]
+|-
+|}
+== Time Complexity Graph ==
 [[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Arbitrary Weights - Time.png|1000px]]
-== Space Complexity graph ==
+== Space Complexity Graph ==
 [[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Arbitrary Weights - Space.png|1000px]]
-== Pareto Decades graph ==
+== Pareto Frontier Improvements Graph ==
 [[File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Graphs with Arbitrary Weights - Pareto Frontier.png|1000px]]