6 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…
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…
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 que…
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…
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…