contents
|
|
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
the flow uses. It can split in small flow portions along a high
number of paths. Many applications do not allow an arbitrary high
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 in 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 in too many packages. Therefore, some applications require that
the flow does not split in too many paths. This motivates so called
k-splittable flows - flows with the requirement to be decomposable in a
given number of paths k.
Our work:
2004:
- Ronald Koch, Ines Spenke,
Complexity and Approximability of k-splittable flow
problems, submitted
- 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
|
top