7 papers
A Faster Undirected Single-Source Shortest Path Algorithm
Avi Kadria, Liam Roditty
The single-source shortest paths (SSSP) problem in graphs with non-negative edge weights is one of the most classic problems in algorithms. For decades, the best known running time…
Improved Approximation Algorithms for n-Pairs Shortest Paths
Avi Kadria, Liam Roditty, Virginia Vassilevska Williams
Let be a graph with nodes and edges. The -Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distan…
Tighter bounds for weighted and unweighted shortest cycle approximation
Avi Kadria, Liam Roditty, Virginia Vassilevska Williams
We study the problem of approximating the length of a shortest cycle in a given graph, known as the girth of the graph. The state-of-the-art approximation algorithms for unweighted…
New approximate distance oracles and their applications
Avi Kadria, Liam Roditty
Let be an undirected graph with vertices and edges, and let . A \emph{distance oracle} is a data structure designed to answer approximate distance quer…
Improved girth approximation in weighted undirected graphs
Avi Kadria, Liam Roditty, Aaron Sidford +2
Let be a -node -edge weighted undirected graph, where is a real \emph{length} function defined on its edges, and let den…
Faster Algorithms for -Stretch Distance Oracles
Avi Kadria, Liam Roditty
Let be an undirected -vertices -edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a -stretch dist…
Compact routing schemes in undirected and directed graphs
Avi Kadria, Liam Roditty
In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs. \textit{For weighted undirected graphs}, more than a decade ago, Chechik…