2026-07-24T05:47:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14608 2024-03-06T10:54:26Z ddc:004 open_access

All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error Chan, Timothy M. Shortest paths approximation matrix multiplication 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(n^{2.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+ω²)/(ω+1)}) ≤ O(n^{2.559}) time for any constant ε > 0. If ω = 2, the time bound is Õ(n^{7/3}), matching a previous result for undirected graphs by Dor, Halperin, and Zwick (2000) which only guaranteed additive error at most 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.27 urn:nbn:de:0030-drops-146086 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.27 eng https://creativecommons.org/licenses/by/4.0/legalcode