Virginia Vassilevska Williams

collaborators

8 papers

cs.DS2026

Improved Approximation Algorithms for n-Pairs Shortest Paths

Avi Kadria, Liam Roditty, Virginia Vassilevska Williams

Let $G = (V, E)$ be a graph with $n = ∣ V ∣$ nodes and $m = ∣ E ∣$ edges. The $t$ -Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distan…

cs.DS2026

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…

cs.DS2026

Witness-Sensitive Detection of Induced Diamonds

Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams +1

We provide a fast \emph{witness-sensitive} algorithm for detecting an induced diamond (a $K_{4}$ minus an edge) in an $n$ -vertex graph containing $t$ induced diamonds. Our algorithm…

cs.DS2026

Undirected Replacement Paths: Dual Fault Reduces to Single Source

Jakob Nogler, Virginia Vassilevska Williams

Given a graph and two fixed vertices $s$ and $t$ , the Replacement Path Problem (RP) is to compute for every edge $e$ , the distance between $s$ and $t$ when $e$ is removed. There ar…

cs.DS2026

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…

cs.DS2024

Listing 6-Cycles in Sparse Graphs

Virginia Vassilevska Williams, Alek Westover

This work considers the problem of output-sensitive listing of occurrences of $2 k$ -cycles for fixed constant $k \geq 2$ in an undirected host graph with $m$ edges and $t$ $2 k$ -cycle…