TY - GEN

T1 - All-pairs shortest paths for real-weighted undirected graphs with small additive error

AU - Chan, Timothy M.

N1 - Publisher Copyright:
© Timothy M. Chan; licensed under Creative Commons License CC-BY 4.0

PY - 2021/9/1

Y1 - 2021/9/1

N2 - Given a graph with n vertices and real edge weights in [0, 1], we investigate an approximate version of the standard all-pairs shortest paths (APSP) problem where distances are estimated with additive error at most ε. Yuster (2012) introduced this natural variant of approximate APSP, and presented an algorithm for directed graphs running in Õ(n(3+ω)/2) ≤ O(n2.687) time for an arbitrarily small constant ε > 0, where ω denotes the matrix multiplication exponent. We give a faster algorithm for undirected graphs running in Õ(n(3+ω2)/(ω+1)) ≤ O(n2.559) time for any constant ε > 0. If ω = 2, the time bound is Õ(n7/3), matching a previous result for undirected graphs by Dor, Halperin, and Zwick (2000) which only guaranteed additive error at most 2.

AB - Given a graph with n vertices and real edge weights in [0, 1], we investigate an approximate version of the standard all-pairs shortest paths (APSP) problem where distances are estimated with additive error at most ε. Yuster (2012) introduced this natural variant of approximate APSP, and presented an algorithm for directed graphs running in Õ(n(3+ω)/2) ≤ O(n2.687) time for an arbitrarily small constant ε > 0, where ω denotes the matrix multiplication exponent. We give a faster algorithm for undirected graphs running in Õ(n(3+ω2)/(ω+1)) ≤ O(n2.559) time for any constant ε > 0. If ω = 2, the time bound is Õ(n7/3), matching a previous result for undirected graphs by Dor, Halperin, and Zwick (2000) which only guaranteed additive error at most 2.

KW - Approximation

KW - Matrix multiplication

KW - Shortest paths

UR - http://www.scopus.com/inward/record.url?scp=85115116264&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115116264&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2021.27

DO - 10.4230/LIPIcs.ESA.2021.27

M3 - Conference contribution

AN - SCOPUS:85115116264

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 29th Annual European Symposium on Algorithms, ESA 2021

A2 - Mutzel, Petra

A2 - Pagh, Rasmus

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 29th Annual European Symposium on Algorithms, ESA 2021

Y2 - 6 September 2021 through 8 September 2021

ER -