Prof. Martin Skutella
TU Berlin

Unsplittable and k-splittable flows in single-source networks

Given a network with a single source and several sinks with associated demands, we study flow problems with restrictions on the flow-carrying paths. In the unsplittable flow problem, the demand of each sink has to be satisfied along a single source-sink path. The $k$-splittable flow problem allows to split each demand into at most $k$ packets such that each packet is sent along a single source-sink path. We discuss recent results and algorithms for turning an arbitrary flow into an unsplittable or $k$-splittable flow with bounded increase of flow values along arcs.