On December 12, 2012, Prof. Dr. Martin Skutella will give a talk about "Unsplittable and k-splittable flows in single-source networks" in the context of the SFB 901 colloquium.
Abstract:
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.