1 Search Results for "Akav, Maor"

Document
DOI: 10.4230/LIPIcs.ESA.2021.4
A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs

Authors: Maor Akav and Liam Roditty

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Let G = (V,E) be a weighted undirected graph with n vertices and m edges, and let d_G(u,v) be the length of the shortest path between u and v in G. In this paper we present a unified approach for obtaining algorithms for all pairs approximate shortest paths in weighted undirected graphs. For every integer k ≥ 2 we show that there is an Õ(n²+kn^{2-3/k}m^{2/k}) expected running time algorithm that computes a matrix M such that for every u,v ∈ V: d_G(u,v) ≤ M[u,v] ≤ (2+(k-2)/k)d_G(u,v). Previous algorithms obtained only specific approximation factors. Baswana and Kavitha [FOCS 2006, SICOMP 2010] presented a 2-approximation algorithm with expected running time of Õ(n²+m√ n) and a 7/3-approximation algorithm with expected running time of Õ(n²+m^{2/3}n). Their results improved upon the results of Cohen and Zwick [SODA 1997, JoA 2001] for graphs with m = o(n²). Kavitha [FSTTCS 2007, Algorithmica 2012] presented a 5/2-approximation algorithm with expected running time of Õ(n^{9/4}). For k = 2 and k = 3 our result gives the algorithms of Baswana and Kavitha. For k = 4, we get a 5/2-approximation algorithm with Õ(n^{5/4}m^{1/2}) expected running time. This improves upon the running time of Õ(n^{9/4}) due to Kavitha, when m = o(n²). Our unified approach reveals that all previous algorithms are a part of a family of algorithms that exhibit a smooth tradeoff between approximation of 2 and 3, and are not sporadic unrelated results. Moreover, our new algorithm uses, among other ideas, the celebrated approximate distance oracles of Thorup and Zwick [STOC 2001, JACM 2005] in a non standard way, which we believe is of independent interest, due to their extensive usage in a variety of applications.
Cite as

Maor Akav and Liam Roditty. A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{akav_et_al:LIPIcs.ESA.2021.4,
  author =	{Akav, Maor and Roditty, Liam},
  title =	{{A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{4:1--4:18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.4},
  URN =		{urn:nbn:de:0030-drops-145858},
  doi =		{10.4230/LIPIcs.ESA.2021.4},
  annote =	{Keywords: Graph algorithms, Approximate All Pairs of Shortest Paths, Distance Oracles}
}
  • Refine by Author
  • 1 Akav, Maor
  • 1 Roditty, Liam

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Approximate All Pairs of Shortest Paths
  • 1 Distance Oracles
  • 1 Graph algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact