(5/3)-approximate ap-shortest paths: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:(5/3)-approximate ap-shortest paths (All-Pairs Shortest Paths (APSP))}} == Description == Approximate APSP within a factor of 5/3. == 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 Dense Undirected Graphs with Positive Integer Weights, APSP on Sparse Directed Graphs with...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: number of vertices | |||
m: number of edges | |||
$m$: number of edges | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:52, 10 April 2023
Description
Approximate APSP within a factor of 5/3.
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 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
Parameters
$n$: number of vertices
$m$: number of edges
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| BMM | assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ |
2017 | https://arxiv.org/pdf/1703.01638.pdf | link |