Flow Increment through Network Expansion

Adrian Marius Deaconu and Luciana Majercsik
Additional contact information
Adrian Marius Deaconu: Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science, Transilvania University of Brasov, 50003 Brasov, Romania
Luciana Majercsik: Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science, Transilvania University of Brasov, 50003 Brasov, Romania

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

Abstract: The network expansion problem is a very important practical optimization problem when there is a need to increment the flow through an existing network of transportation, electricity, water, gas, etc. In this problem, the flow augmentation can be achieved either by increasing the capacities on the existing arcs, or by adding new arcs to the network. Both operations are coming with an expansion cost. In this paper, the problem of finding the minimum network expansion cost so that the modified network can transport a given amount of flow from the source node to the sink node is studied. A strongly polynomial algorithm is deduced to solve the problem.

Keywords: network flow; flow increment; network expansion (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/18/2308/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/18/2308/ (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:18:p:2308-:d:638616

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