*k*-splittable Flows

In classic flow theory flow is sent through a network from sources
to sinks respecting edge capacities. It does not matter how many
paths are used. The flow can split in small flow portions along a
high number of paths. Many applications do not allow an arbitrary
number of paths. For example, in logistics goods should be
transported with a given number of trucks. This given number
limits the number of paths which can be used
simultaneously. Another example is the transport of data in
communication networks. Many communication systems split data into
packages, for example the internet. These packages traverse the
network along different paths. Every package has to carry full
information about source and target of the data, about the
position of this package among other packages, and so on. It is
not efficient to split data into too many packages. Therefore, some
applications require that the flow does not split into too many
paths. This motivates so called *k-splittable flows* - flows
with the requirement to be decomposable into a given number of paths
*k*.

**Publications:**

2006

- Ines Spenke, Complexity and Approximation of Static k-Splittable Flows and Dynamic Grid Flows, PhD thesis
- Ronald Koch, Martin Skutella and Ines Spenke, Maximum k-splittable s,t-flows, to appear in Theory of Computing Systems
- Ronald Koch and Ines Spenke, Complexity and approximability of k-splittable flows, Theoretical Computer Science

2005

- Ronald Koch, Martin Skutella, and Ines Spenke, Approximation and complexity of k-splittable flows, WAOA 2005

2004

- Ronald Koch, Komplexitaet und Approximierbarkeit von k-spaltbaren Fluessen, Diploma Thesis

2003

- Georg Baier, Flows with path restrictions, PhD thesis
- Georg Baier, Ekkehard Köhler, and Martin Skutella, On the k-splittable flow problem, ESA 2002
- Maren Martens, The unsplittable flow problem and generalizations, Diploma thesis

**See also:**