Aditi Dudeja, Rutgers University

Abstract

The all-pairs minimum-cut size problem asks for a minimum s-t cut over all pairs of vertices s, t. This can clearly be solved in time O(n^2 T) where T is the time take for computing a minimum s-t cut for any given s,t. Gomory and Hu showed that for undirected graphs it can be done faster, and there is a concise structure, the Gomory-Hu tree to represent all minimum cuts. In this talk, I will prove that for any graph G, a Gomory-Hu tree exists and can be found using n-1 min-cut computations. 

Presented via Zoom - Meeting ID: 984 4140 9199

https://rutgers.zoom.us/j/98441409199

Password: 715004