TY - RPRT
A1 - Beygang, Katharina
A1 - Krumke, Sven O.
A1 - Zeck, Christiane
T1 - Generalized Max Flow in Series-Parallel Graphs
N2 - 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(m*m) time and a dynamic programming algorithm with running time O(m*log(m)) that only computes the maximum flow value but not the flow itself. For the integral version of the problem, which is known to be NP-complete, we present a pseudo-polynomial algorithm.
T3 - Report in Wirtschaftsmathematik (WIMA Report) - 125
Y1 - 2010
UR - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2179
UR - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-16365
ER -