APSP on Geometrically Weighted Graphs: Difference between revisions
(Created page with "{{DISPLAYTITLE:APSP on Geometrically Weighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Dense Undirected Graph...") |
No edit summary |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: number of vertices | |||
m: number of edges | |||
c: number of weights | $m$: number of edges | ||
$c$: number of unique weights | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 24: | Line 26: | ||
|- | |- | ||
| [[Chan (Geometrically Weighted) (APSP on Geometrically Weighted Graphs All-Pairs Shortest Paths (APSP))|Chan (Geometrically Weighted)]] || 2009 || $O( | | [[Chan (Geometrically Weighted) (APSP on Geometrically Weighted Graphs All-Pairs Shortest Paths (APSP))|Chan (Geometrically Weighted)]] || 2009 || $O(n^{2.{84}4})$ || $O(l n^{2})$ || Exact || Deterministic || [http://tmc.web.engr.illinois.edu/moreapsp.pdf Time] | ||
|- | |- | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:All-Pairs Shortest Paths (APSP) - APSP on Geometrically Weighted Graphs - Time.png|1000px]] | [[File:All-Pairs Shortest Paths (APSP) - APSP on Geometrically Weighted Graphs - Time.png|1000px]] | ||
Latest revision as of 10:06, 28 April 2023
Description
In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values.
Related Problems
Generalizations: APSP
Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Positive Integer Weights, 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
$c$: number of unique weights
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Chan (Geometrically Weighted) | 2009 | $O(n^{2.{84}4})$ | $O(l n^{2})$ | Exact | Deterministic | Time |
Time Complexity Graph
_-_APSP_on_Geometrically_Weighted_Graphs_-_Time.png)