|
Modelirovanie i Analiz Informatsionnykh Sistem, 2012, Volume 19, Number 2, Pages 41–52
(Mi mais218)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Flows in generalized nets with related arcs
V. A. Skorokhodov Southern Federal University, Rostov-on-Don
Abstract:
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.
Keywords:
graph, graph algorithms, reachability, nonstandard reachability, flows on nets.
Received: 03.11.2011
Citation:
V. A. Skorokhodov, “Flows in generalized nets with related arcs”, Model. Anal. Inform. Sist., 19:2 (2012), 41–52
Linking options:
https://www.mathnet.ru/eng/mais218 https://www.mathnet.ru/eng/mais/v19/i2/p41
|
|