(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 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