Seminar Details
Gomory-Hu Trees
- Start Date: December 9, 2020
- Event Start Time: 12:15 PM
- Event End Time: 1:15 PM
- Seminar Series: Graduate Combinatorics Seminar
- Presenter(s): Aditi Dudeja - Rutgers University
- Event Location: Online Event
- Event Additional Info: <p>Presented via Zoom - Meeting ID: 984 4140 9199</p> <p><a href="https://nam02.safelinks.protection.outlook.com/?url=https%3A%2F%2Frutgers.zoom.us%2Fj%2F98441409199&data=04%7C01%7C%7C65c3d8ec010f460475f508d884c456b1%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C637405326087432669%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=o16NJyf9SZ0ksckMoobsChi5qNj4oc%2Fz4Uk%2BRaetqQc%3D&reserved=0">https://rutgers.zoom.us/j/98441409199</a></p> <p> </p> <p>Password: 715004</p> <p> </p>
- Presentation Type: Stand Alone Presentation
- 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.