24 citations · 59 across the 29 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder
We present a new and surprisingly simple analysis of random-shift decompositions -- originally proposed by Miller, Peng, and Xu [SPAA'13]: We show that decompositions for exponenti…
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 , 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…