Wuwei Yuan

collaborators

3 papers

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…

cs.DS2023

Maximal $k$ -Edge-Connected Subgraphs in Almost-Linear Time for Small $k$

Thatchaphol Saranurak, Wuwei Yuan

We give the first almost-linear time algorithm for computing the \emph{maximal $k$ -edge-connected subgraphs} of an undirected unweighted graph for any constant $k$ . More specifical…

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

Deterministic Almost-Linear-Time Gomory-Hu Trees

Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k

Maximal $k$ -Edge-Connected Subgraphs in Almost-Linear Time for Small $k$