Begin: Wed, 12. of Dec 2012 ( 6:00 PM)
Location: Fürstenallee 11, Room F0.530
On December 12, 2012, Prof. Dr. Martin Skutella will give a talk in the context of the SFB 901 colloquium. Title: Unsplittable and k-splittable flows in single-source networks
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.
