3 citations · 8 across the 9 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
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…
cs.DS2018
Faster Algorithms for All-Pairs Bounded Min-Cuts
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano +5
The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum - cut (or just its value) for all pairs of vertices . We study this problem in directed…
cs.DS2018
Nearly Optimal Time Bounds for kPath in Hypergraphs
Lior Kamma, Ohad Trabelsi
We give almost tight conditional lower bounds on the running time of the kHyperPath problem. Given an -uniform hypergraph for some integer , kHyperPath seeks a tight path of…