2 papers
cs.DS2026
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan +1
Given an undirected graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree on that preserves all-pairs mincuts of exactly. We present a simple, efficient r…
cs.DS2025
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li +5
Given an -edge, undirected, weighted graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree over the vertex set such that all-pairs mincuts in are prese…