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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Katharina Beygang, Sven O. Krumke, Christiane Zeck
URN (permanent link):urn:nbn:de:hbz:386-kluedo-16365
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (125)
Document Type:Report
Language of publication:English
Year of Completion:2010
Year of Publication:2010
Publishing Institute:Technische Universität Kaiserslautern
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $