文章基本信息

标题：All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error
本地全文：下载
作者：Chan, Timothy M.
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：204
DOI：10.4230/LIPIcs.ESA.2021.27
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Õ(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 Õ(n^{(3+ω²)/(ω+1)}) ≤ O(n^{2.559}) time for any constant ε > 0. If ω = 2, the time bound is Õ(n^{7/3}), matching a previous result for undirected graphs by Dor, Halperin, and Zwick (2000) which only guaranteed additive error at most 2.
关键词：Shortest paths;approximation;matrix multiplication