1 citations · 2 across the 2 of their papers we have counts for
8 papers
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…
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…
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…
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…
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
We investigate the time-complexity of the All-Pairs Max-Flow problem: Given a graph with nodes and edges, compute for all pairs of nodes the maximum-flow value between them…
Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
We reprove three known algorithmic bounds for terminal-clustering problems, using a single framework that leads to simpler proofs. In this genre of problems, the input is a metric…