Applied Mathematics

Volume 4, Issue 10 (October 2013)

ISSN Print: 2152-7385   ISSN Online: 2152-7393

Google-based Impact Factor: 0.58  Citations  

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.

Cited by

[1] Maximum Flow by Network Reconstruction Method
International Conference on …, 2023
[2] Automated Identification and Tracking of Motile Oligodendrocyte Precursor Cells (OPCs) from Time-lapse 3D Microscopic Imaging Data of Cell Clusters in vivo
2021
[3] Minimum Flows in Parametric Dynamic Networks-the Static Approach.
2020
[4] Minimum Flows in Parametric Dynamic Networks. The Static Approach
2020
[5] PARAMETRIC FLOWS IN STATIC NETWORKS
2019
[6] Minimum parametric flow in time-dependent dynamic networks
2018
[7] The maximum flows in parametric dynamic networks
2017
[8] The Maximum Parametric Flow in Discrete-time Dynamic Networks
Fundamenta Informaticae, 2017
[9] Maximum flows in parametric dynamic networks with lower bounds
2016
[10] Minimum Parametric Flow–A Partitioning Approach
Br. J. Appl. Sci. Technol., 2016
[11] Minimum parametric flow. A partitioning approach
2016
[12] Minimum parametric flow over time
arXiv preprint arXiv:1509.03817, 2015
[13] A Preflow Approach to Maximum Flows in Parametric Networks Applied to Assessing the Legal Information
International Journal of Computers Communications & Control, 2015
[14] MAXIMUM FLOW OVER TIME PROBLEM IN PARAMETRIC NETWORKS.
Bulletin of the Transilvania University of Brasov, Series III: Mathematics, Informatics, Physics, 2014
[15] MAXIMUM FLOW OVER TIME PROBLEM IN PARAMETRIC NETWORKS
Bulletin of the Transilvania University of Brasov, 2014
[16] TITLU TEZEI: FLUXURI PARAMETRICE ÎN REȚELE DINAMICE

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.