9 citations · 22 across the 13 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
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…