All-pairs shortest paths with a sublinear additive error

DOI10.1145/2000807.2000813zbMath1295.68138OpenAlexW1994717376WikidataQ130986753 ScholiaQ130986753MaRDI QIDQ3189029

Liam Roditty, Asaf Shapira

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2000807.2000813

zbMATH Keywords

shortest pathsgraph algorithmsmatrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

On random perfect matchings in metric spaces with not-too-large diameters ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ Improved distance queries and cycle counting by Frobenius normal form

This page was built for publication: All-pairs shortest paths with a sublinear additive error