Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Space Complexity of Minimum Cut Problems in Single-Pass Streams
Matthew Ding, Alexandro Garces, Jason Li +4
We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the spec…
cs.DS2024
Deterministic Minimum Steiner Cut in Maximum Flow Time
Matthew Ding, Jason Li
We devise a deterministic algorithm for minimum Steiner cut, which uses maximum flow calls and additional near-linear time. This algorithm improves on Li and Pani…