Flows in Generalized Nets with Related Arcs
The problem of finding the maximum flow in nets of a special form is considered. In such nets the arcs are related in such a way that the total flow passing through the related arcs does not exceed the minimum throughput of these arcs. It is shown that the theorem by Ford and Fulkerson, according to...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2015-02-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/17 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850023898004848640 |
|---|---|
| author | V. A. Skorokhodov |
| author_facet | V. A. Skorokhodov |
| author_sort | V. A. Skorokhodov |
| collection | DOAJ |
| description | The problem of finding the maximum flow in nets of a special form is considered. In such nets the arcs are related in such a way that the total flow passing through the related arcs does not exceed the minimum throughput of these arcs. It is shown that the theorem by Ford and Fulkerson, according to which the maximum flux value is equal to the throughput of a minimum cut, is not performed for such networks. The estimations of the maximum flow in a generalized net with bound arcs are proposed. And the algorithm for finding the maximum flow in such nets is developed. |
| format | Article |
| id | doaj-art-6b3de37a64624b7d95cbc583a3c6ca0d |
| institution | DOAJ |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2015-02-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-6b3de37a64624b7d95cbc583a3c6ca0d2025-08-20T03:01:15ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172015-02-01192415210.18255/1818-1015-2012-2-41-5211Flows in Generalized Nets with Related ArcsV. A. Skorokhodov0Южный федеральный университетThe problem of finding the maximum flow in nets of a special form is considered. In such nets the arcs are related in such a way that the total flow passing through the related arcs does not exceed the minimum throughput of these arcs. It is shown that the theorem by Ford and Fulkerson, according to which the maximum flux value is equal to the throughput of a minimum cut, is not performed for such networks. The estimations of the maximum flow in a generalized net with bound arcs are proposed. And the algorithm for finding the maximum flow in such nets is developed.https://www.mais-journal.ru/jour/article/view/17graphgraph algorithmsreachabilitynonstandard reachabilityflows on nets |
| spellingShingle | V. A. Skorokhodov Flows in Generalized Nets with Related Arcs Моделирование и анализ информационных систем graph graph algorithms reachability nonstandard reachability flows on nets |
| title | Flows in Generalized Nets with Related Arcs |
| title_full | Flows in Generalized Nets with Related Arcs |
| title_fullStr | Flows in Generalized Nets with Related Arcs |
| title_full_unstemmed | Flows in Generalized Nets with Related Arcs |
| title_short | Flows in Generalized Nets with Related Arcs |
| title_sort | flows in generalized nets with related arcs |
| topic | graph graph algorithms reachability nonstandard reachability flows on nets |
| url | https://www.mais-journal.ru/jour/article/view/17 |
| work_keys_str_mv | AT vaskorokhodov flowsingeneralizednetswithrelatedarcs |