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.






See also: