RETRACTED: A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

Society for Industrial and Applied Mathematics eBooks 2026

View at publisher
Authors: Maximilian Probst Gutenberg, Rasmus Kyng, Wei Yuan, Wuwei Yuan
DOI: 10.1137/1.9781611978971.139
Cited by: 0

Abstract

Given an undirected graph \(G = (V, E, w)\), a Gomory-Hu tree \(T\) (Gomory and Hu, 1961) is a tree on \(V\) that preserves all-pairs mincuts of \(G\) exactly.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Graph Theory and Algorithms Topological and Geometric Data Analysis

Publication details

Journal / source
Society for Industrial and Applied Mathematics eBooks
Pages
3805–3819
Publication date
1 January 2026
Language
EN