4 papers
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…
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…
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…
On the Bidirected Cut Relaxation for Steiner Forest
Jarosław Byrka, Fabrizio Grandoni, Vera Traub
The Steiner Forest problem is an important generalization of the Steiner Tree problem. We are given an undirected graph with nonnegative edge costs and a collection of pairs of ver…