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.
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: