ARC Colloquium: Debmalya Panigrahi (Duke University)

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. 

---------------------------------------------------------------

Speaker's Webpage

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

Event Details

Date/Time:

  • Monday, October 10, 2022
    11:00 am - 12:00 pm
Location: Klaus 1116