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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772044
DOIs
StatePublished - Sep 1 2021
Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
Duration: Sep 6 2021Sep 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume204
ISSN (Print)1868-8969

Conference

Conference29th Annual European Symposium on Algorithms, ESA 2021
Country/TerritoryPortugal
CityVitual, Lisbon
Period9/6/219/8/21

Keywords

  • Approximation
  • Matrix multiplication
  • Shortest paths

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'All-pairs shortest paths for real-weighted undirected graphs with small additive error'. Together they form a unique fingerprint.

Cite this