Nathan Klein

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

Thin Trees for Near Minimum Cuts

Nathan Klein, Neil Olver, Zi Song Yeoh

The strong thin tree conjecture states that every $k$ -edge-connected graph $G$ contains an $O (1/ k)$ -thin spanning tree, meaning a spanning tree which contains at most an $O (1/ k)$ f…

cs.DS2026

A Strong Linear Programming Relaxation for Weighted Tree Augmentation

Vincent Cohen-Addad, Marina Drygala, Nathan Klein +1

The Weighted Tree Augmentation Problem (WTAP) is a fundamental network design problem where the goal is to find a minimum-cost set of additional edges (links) to make an input tree…

cs.DS2024

Ghost Value Augmentation for $k$ -Edge-Connectivity

D Ellis Hershkowitz, Nathan Klein, Rico Zenklusen

We give a poly-time algorithm for the $k$ -edge-connected spanning subgraph ( $k$ -ECSS) problem that returns a solution of cost no greater than the cheapest $(k + 10)$ -ECSS on the same…

Thin Trees for Near Minimum Cuts

A Strong Linear Programming Relaxation for Weighted Tree Augmentation

Ghost Value Augmentation for k-Edge-Connectivity

Ghost Value Augmentation for $k$ -Edge-Connectivity