3 citations · 4 across the 11 of their papers we have counts for
13 papers
When Shall We Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance
Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova +1
Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computati…
The Cost of Changing Edges for Diameter Computation and More
Sam Hiken, Yael Kirkpatrick, Jakob Nogler +1
The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time mo…
Improved Approximation of Min-Distances in Near-Linear Time
Yael Kirkpatrick
We study the problem of approximating the diameter of directed graphs under the min-distance measure, defined as . Unlike standard shortest-pa…
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…
Preprocessed 3SUM for Unknown Universes with Subquadratic Space
Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan +1
We consider the classic 3SUM problem: given sets of integers , determine whether there is a tuple satisfying . The 3SUM…
Improved Additive Approximation Algorithms for APSP
Ce Jin, Yael Kirkpatrick, Michał Stawarz +1
The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, b…
Shortest Paths in Multimode Graphs
Yael Kirkpatrick, Virginia Vassilevska Williams
In this work we study shortest path problems in multimode graphs, a generalization of the min-distance measure introduced by Abboud, Vassilevska W. and Wang in [SODA'16]. A multimo…
Beyond 2-approximation for k-Center in Graphs
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams +1
We consider the classical -Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even -approximations r…
A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms
Yael Kirkpatrick, Surya Mathialagan
In a seminal work, Chiba and Nishizeki [SIAM J. Comput. `85] developed subgraph listing algorithms for triangles, 4-cycle and -cliques, where The runtimes of their a…
Graph Threading with Turn Costs
Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin
How should we thread a single string through a set of tubes so that pulling the string taut self-assembles the tubes into a desired graph? While prior work [ITCS 2024] solves this…
Graph Threading
Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin
Inspired by artistic practices such as beadwork and himmeli, we study the problem of threading a single string through a set of tubes, so that pulling the string forms a desired gr…
Fast 2-Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yael Kirkpatrick +3
In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for -approximate A…
The -Rank and Size of Graphs
Gal Beniamini, Asaf Etgar, Yael Kirkpatrick
We consider the extremal family of graphs of order in which no two vertices have identical neighbourhoods, yet the adjacency matrix has rank only over the field of two el…