Showing 2025Show all
2 papers · 1 filter
cs.DS2025
Minimum -- Cuts with Fewer Cut Queries
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
We study the problem of computing a minimum -- cut in an unweighted, undirected graph via \emph{cut queries}. In this model, the input graph is accessed through an oracle tha…
cs.DS2025
A (Very) Nearly Optimal Sketch for -Edge Connectivity Certificates
Pachara Sawettamalya, Huacheng Yu
In this note, we present a simple algorithm for computing a \emph{-connectivity certificate} in dynamic graph streams. Our algorithm uses $O(n \log^2 n \cdot \max\{k, \log n \lo…