research
∙
04/10/2023
(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
The All-Pairs Max-Flow problem has gained significant popularity in the ...
share
research
∙
12/22/2022
Bridge Girth: A Unifying Notion in Network Design
A classic 1993 paper by Althőfer et al. proved a tight reduction from sp...
research
∙
11/09/2021
Gomory-Hu Tree in Subcubic Time
In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...
research
∙
10/29/2021
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
We devise new cut sparsifiers that are related to the classical sparsifi...
research
∙
06/05/2021
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
We design an n^2+o(1)-time algorithm that constructs a cut-equivalent (G...
research
∙
12/18/2020
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Every undirected graph G has a (weighted) cut-equivalent tree T, commonl...
research
∙
09/13/2020
Cut-Equivalent Trees are Optimal for Min-Cut Queries
Min-Cut queries are fundamental: Preprocess an undirected edge-weighted ...
research
∙
01/05/2019
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
We investigate the time-complexity of the All-Pairs Max-Flow problem: Gi...
research
∙
09/04/2018
Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
We reprove three known algorithmic bounds for terminal-clustering proble...
research
∙
09/04/2018
Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems
We reprove three known (algorithmic) bounds for terminal-clustering prob...
research
∙
07/16/2018
Faster Algorithms for All-Pairs Bounded Min-Cuts
Given a directed graph, the vertex connectivity from u to v is the maxim...
research
∙
03/13/2018
Nearly Optimal Time Bounds for kPath in Hypergraphs
In the kPath problem the input is a graph G and an integer k, and the go...
research
∙
11/21/2017