225 citations · 759 across the 35 of their papers we have counts for
42 papers
Cut query algorithms with star contraction
Simon Apers, Yuval Efron, Paweł Gawrychowski +3
We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that (i) there is a bounded-error randomized algorithm that computes edge c…
Finding the KT partition of a weighted graph in near-linear time
Simon Apers, Paweł Gawrychowski, Troy Lee
In a breakthrough work, Kawarabayashi and Thorup (J.~ACM'19) gave a near-linear time deterministic algorithm for minimum cut in a simple graph . A key component is findi…
A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
Simon Apers, Arinta Auza, Troy Lee
An minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices and . Finding such a cut is a classic pro…
On the query complexity of connectivity with global queries
Arinta Auza, Troy Lee
We study the query complexity of determining if a graph is connected with global queries. The first model we look at is matrix-vector multiplication queries to the adjacency matrix…
On the cut dimension of a graph
Troy Lee, Tongyang Li, Miklos Santha +1
Let be a weighted undirected graph with edges. The cut dimension of is the dimension of the span of the characteristic vectors of the minimum cuts of , viewe…
Quantum complexity of minimum cut
Simon Apers, Troy Lee
The minimum cut problem in an undirected and weighted graph is to find the minimum total weight of a set of edges whose removal disconnects . We completely characterize the…