Weixuan Yuan

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2025

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition

Maximilian Probst Gutenberg, Weixuan Yuan

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. We present a simple and efficien…

cs.DS2025

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

Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan +1

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. We present a simple, efficient r…

cs.DS2025

Deterministic Almost-Linear-Time Gomory-Hu Trees

Amir Abboud, Rasmus Kyng, Jason Li +5

Given an $m$ -edge, undirected, weighted graph $G = (V, E, w)$ , a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are prese…