Incremental Minimum Flow Algorithms
| Autor: | Adrian Deaconu, Laura Ciupala |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Computer science
General Mathematics Computation Minor (linear algebra) decreasing path algorithms 0211 other engineering and technologies 02 engineering and technology Upper and lower bounds Arc (geometry) network flows incremental algorithms QA1-939 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Engineering (miscellaneous) computer.programming_language 021103 operations research minimum flow Flow network Flow (mathematics) Scratch Combinatorial optimization combinatorial optimization 020201 artificial intelligence & image processing computer Algorithm Mathematics |
| Zdroj: | Mathematics, Vol 9, Iss 1025, p 1025 (2021) Mathematics Volume 9 Issue 9 |
| ISSN: | 2227-7390 |
| DOI: | 10.3390/math9091025 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|