RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2012 Volume 19, Number 2, Pages 41–52 (Mi mais218)

This article is cited 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.

UDC: 519.1

Received: 03.11.2011



© Steklov Math. Inst. of RAS, 2024