3 papers
cs.DS2026
Thin Trees for Near Minimum Cuts
Nathan Klein, Neil Olver, Zi Song Yeoh
The strong thin tree conjecture states that every -edge-connected graph contains an -thin spanning tree, meaning a spanning tree which contains at most an 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.DS2023
Ghost Value Augmentation for -Edge-Connectivity
D Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
We give a poly-time algorithm for the -edge-connected spanning subgraph (-ECSS) problem that returns a solution of cost no greater than the cheapest -ECSS on the same…