Generalized max flow in series–parallel graphs

In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node reaches its head node. We consider this problem for the class of series–parallel graphs. First, we study the continuous case of the problem and prove that it can be solved using a greedy approach. Based on this result, we present a combinatorial algorithm that runs in O(nm+mlogm)O(nm+mlogm) time, where mm is the number of arcs, and a dynamic programming algorithm with running time O(mlogm)O(mlogm). For the integral version of the problem, which is known to be NPNP-complete, we present a pseudo-polynomial algorithm.