3 papers
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…
cs.DS2025
Fast Algorithms for Graph Arboricity and Related Problems
Ruoxu Cen, Henry Fleischmann, George Z. Li +2
We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m…
cs.DS2025
Network Unreliability in Almost-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
The network unreliability problem asks for the probability that a given undirected graph gets disconnected when every edge independently fails with a given probability . Valiant…