3
votes
Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time
The discussion in this paper, Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
graph-algorithms × 982graph-theory × 513
ds.algorithms × 323
cc.complexity-theory × 135
reference-request × 102
approximation-algorithms × 71
np-hardness × 69
co.combinatorics × 61
optimization × 46
shortest-path × 46
directed-acyclic-graph × 44
planar-graphs × 37
clique × 32
ds.data-structures × 27
matching × 27
graph-isomorphism × 26
time-complexity × 24
tree × 23
parameterized-complexity × 23
counting-complexity × 22
graph-colouring × 22
treewidth × 20
fixed-parameter-tractable × 20
linear-programming × 19
partition-problem × 15