*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Debmalya Panigrahi (Duke University)
October 10, 2022
Klaus 1116 - 11:00 am
Title: All-Pairs Minimum Cuts in Nearly Quadratic Time
Abstract: In 1961, Gomory and Hu showed the surprising result that minimum cuts between all pairs of vertices in an undirected graph can be retrieved from only a linear number of (single-pair) minimum cut computations. This has remained the state-of-the-art for the all-pairs minimum cuts problem for the last 60 years, and takes at least cubic time in the number of vertices. In this talk, I will give a new algorithm that breaks this longstanding barrier and solves the all-pairs minimum cuts problem in nearly quadratic time.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
