License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.27
URN: urn:nbn:de:0030-drops-146086
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14608/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M.

All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error

pdf-format:
LIPIcs-ESA-2021-27.pdf (0.7 MB)

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(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.

BibTeX - Entry

@InProceedings{chan:LIPIcs.ESA.2021.27,
  author =	{Chan, Timothy M.},
  title =	{{All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{27:1--27:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14608},
  URN =		{urn:nbn:de:0030-drops-146086},
  doi =		{10.4230/LIPIcs.ESA.2021.27},
  annote =	{Keywords: Shortest paths, approximation, matrix multiplication}
}

Keywords: Shortest paths, approximation, matrix multiplication
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI