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: and

Click here to subscribe to the seminar email list:

Event Details


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