10 papers
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 algorithms for girth and cycle detection
Liam Roditty, Plia Trabelsi
Let be an unweighted undirected graph with vertices and edges. Let be the girth of , that is, the length of a shortest cycle in . We present a randomize…
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…
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…