A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs

Journal Article

We give an n 2+o(1)-time algorithm for finding s-t min-cuts for all pairs of vertices s and T in a simple, undirected graph on n vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of tildeO(n 2.5}) by Abboud et al. (STOC 2021). Our running time is nearly optimal as a function of n.

Full Text

Duke Authors

Cited Authors

  • Li, J; Panigrahi, D; Saranurak, T

Published Date

  • January 1, 2022

Published In

Volume / Issue

  • 2022-February /

Start / End Page

  • 1124 - 1134

International Standard Serial Number (ISSN)

  • 0272-5428

Digital Object Identifier (DOI)

  • 10.1109/FOCS52979.2021.00111

Citation Source

  • Scopus