Partitioning Algorithm for the Parametric Maximum Flow

HTML  XML Download Download as PDF (Size: 678KB)  PP. 3-10  
DOI: 10.4236/am.2013.410A1002    2,811 Downloads   4,909 Views  Citations

ABSTRACT

The article presents an approach to the maximum flow problem in parametric networks with linear capacity functions of a single parameter, based on the concept of shortest conditional augmenting directed path. In order to avoid working with piecewise linear functions, our approach uses a series of parametric residual networks defined for successive subintervals of the parameter values where the parametric residual capacities of all arcs remain linear functions. Besides working with linear instead piecewise linear functions, another main advantage of our approach is that every directed path in such a parametric residual network is also a conditional augmenting directed path for the subinterval for which the parametric residual network was defined. The complexity of the partitioning algorithm is O (Kn2m) where K is the number of partitioning points of the parameter values interval, n and m being the number of nodes, respectively the number of arcs in the network.

Share and Cite:

M. Parpalea and E. Ciurea, "Partitioning Algorithm for the Parametric Maximum Flow," Applied Mathematics, Vol. 4 No. 10A, 2013, pp. 3-10. doi: 10.4236/am.2013.410A1002.
Journals Menu
Follow SCIRP
Contact us
+1 323-425-8868
customer@scirp.org
WhatsApp +86 18163351462(WhatsApp)
Click here to send a message to me 1655362766
Paper Publishing WeChat

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.