Incremental Minimum Flow Algorithms

Laura Ciupala and Adrian Deaconu
Additional contact information
Laura Ciupala: Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science, Transylvania University of Brasov, 500036 Brasov, Romania
Adrian Deaconu: Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science, Transylvania University of Brasov, 500036 Brasov, Romania

Mathematics, 2021, vol. 9, issue 9, 1-13

Abstract: There are various situations in which real-world problems can be modeled and solved as minimum flow problems. Sometimes, in these situations, minor data changes may occur, leading to corresponding changes of the networks in which the practical problems are modeled as flow problems, such as slight variations in capacity or lower bound. For instance, the capacity or the lower bound of an arc may increase or decrease in time, leaving one with no other choice than finding the new minimum network flow. Given both the various ways in which the networks can be changed and the high frequency of these changes, it is desirable to find as fast a computation method for minimum flow as possible. This paper is focused on the cases that concern increasing and decreasing the capacity or the lower bound of an arc. For these cases, both the minimum flow algorithms and the dynamic minimum flow algorithms that are already known are inefficient. Our incremental algorithms for determining minimum flow in the modified network are more efficient than both the above-mentioned types of algorithms. The proposed method starts from the initial network minimum flow and solves the minimum flow problem in a significantly faster way than recalculating the new network minimum flow starting from scratch.

Keywords: network flows; combinatorial optimization; minimum flow; incremental algorithms; decreasing path algorithms (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/9/1025/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/9/1025/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:9:p:1025-:d:547561

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().