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

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Katharina Beygang, Sven O. Krumke, Christiane Zeck
URN:urn:nbn:de:hbz:386-kluedo-16365
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (125)
Document Type:Report
Language of publication:English
Year of Completion:2010
Year of first Publication:2010
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2010/03/09
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011