19 citations · 67 across the 27 of their papers we have counts for
35 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 Diameter Approximations via Distance Oracle Techniques
Yael Kirkpatrick, Liam Roditty, Richard Qi +1
Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard…
Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
Liam Roditty, Ariel Sapir
We introduce a generalized family of $\left( 2\cdot \left\lfloor \frac{k}{2} \right\rfloor-1, 2\cdot \left\lceil \frac{k}{2} \right\rceil \cdot W_{1} +\max\left\{0,2\cdot\left(\lef…
Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
Liam Roditty, Ariel Sapir
We present a -APASP algorithm for dense weighted graphs with runtime , where is the weight of an $i^{th}…