Abstract

We give a 2-pass semi-streaming algorithm to find the exact global minimum cut of an unweighted, undirected graph. This result is adapted from a paper by Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg called Computing Exact Minimum Cuts Without Knowing the Graph (ITCS 2018).

Biography

Shreya Mogulothu is a junior at West Windsor-Plainsboro High School North. She has been a participant in the Program in Algorithmic and Combinatorial Thinking (PACT) since the summer of 2019. She loves working on problems, especially collaboratively. In her free time, she writes problems with her friends and blogs about things she finds curious.