10 citations · 15 across the 7 of their papers we have counts for
17 papers · 1 filter
Worst-Case to Expander-Case Reductions
Amir Abboud, Nathan Wallheimer
In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful ham…
Listing 4-Cycles
Amir Abboud, Seri Khoury, Oree Leibowitz +1
In this note we present an algorithm that lists all -cycles in a graph in time where is their number. Notably, this separates -cycle list…
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee +1
We study several questions related to diversifying search results. We give improved approximation algorithms in each of the following problems, together with some lower bounds. - W…
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…