Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Approximation Schemes for Planar Graph Connectivity Problems
Meike Neuwohner, Vera Traub, Rico Zenklusen
Finding a smallest subgraph that is k-edge-connected, or augmenting a k-edge-connected graph with a smallest subset of given candidate edges to become (k+1)-edge-connected, are amo…
cs.DS2025
Steiner Forest: A Simplified Better-Than-2 Approximation
Anupam Gupta, Vera Traub
In the Steiner Forest problem, we are given a graph with edge lengths, and a collection of demand pairs; the goal is to find a subgraph of least total length such that each demand…
cs.DS2025
Unsplittable Cost Flows from Unweighted Error-Bounded Variants
Chaitanya Swamy, Vera Traub, Laura Vargas Koch +1
A famous conjecture of Goemans on single-source unsplittable flows states that one can turn any fractional flow into an unsplittable one of no higher cost, while increasing the loa…