3 citations · 8 across the 9 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021★ 1 cited
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
Amir Abboud, Robert Krauthgamer, Jason Li +3
In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all pairs of vertices in an undirected graph can be solved using on…
cs.DS2021
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
We devise new cut sparsifiers that are related to the classical sparsification of Nagamochi and Ibaraki [Algorithmica, 1992], which is an algorithm that, given an unweighted graph…
cs.DS2021★ 1 cited
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
We design an -time algorithm that constructs a cut-equivalent (Gomory-Hu) tree of a simple graph on nodes. This bound is almost-optimal in terms of , and it impr…