3 citations · 8 across the 9 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Every undirected graph has a (weighted) cut-equivalent tree , commonly named after Gomory and Hu who discovered it in 1961. Both and have the same node set, and for…
cs.DS2020
Cut-Equivalent Trees are Optimal for Min-Cut Queries
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Min-Cut queries are fundamental: Preprocess an undirected edge-weighted graph, to quickly report a minimum-weight cut that separates a query pair of nodes . The best data stru…