9 citations · 22 across the 7 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2022★ 1 cited
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…
cs.DS2021
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…
cs.DS2021★ 1 cited
Testing properties of signed graphs
Florian Adriaens, Simon Apers
In graph property testing the task is to distinguish whether a graph satisfies a given property or is "far" from having that property, preferably with a sublinear query and time co…