Adaptation of Random Binomial Graphs for Testing Network Flow Problems Algorithms

Adrian Marius Deaconu and Delia Spridon
Additional contact information
Adrian Marius Deaconu: Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science, Transilvania University of Brasov, 50003 Brașov, Romania
Delia Spridon: Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science, Transilvania University of Brasov, 50003 Brașov, Romania

Mathematics, 2021, vol. 9, issue 15, 1-14

Abstract: Algorithms for network flow problems, such as maximum flow, minimum cost flow, and multi-commodity flow problems, are continuously developed and improved, and so, random network generators become indispensable to simulate the functionality and to test the correctness and the execution speed of these algorithms. For this purpose, in this paper, the well-known Erd?s–Rényi model is adapted to generate random flow (transportation) networks. The developed algorithm is fast and based on the natural property of the flow that can be decomposed into directed elementary s-t paths and cycles. So, the proposed algorithm can be used to quickly build a vast number of networks as well as large-scale networks especially designed for s-t flows.

Keywords: network flow; random networks; parallel programming; time efficiency of algorithms (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/15/1716/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/15/1716/ (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:15:p:1716-:d:598525

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