RUS  ENG
Full version
JOURNALS // Itogi Nauki i Tekhniki. Sovremennaya Matematika i ee Prilozheniya. Tematicheskie Obzory // Archive

Itogi Nauki i Tekhniki. Sovrem. Mat. Pril. Temat. Obz., 2022 Volume 208, Pages 24–28 (Mi into991)

Flows in networks with barrier reachability

I. M. Erusalimskyi, V. A. Skorokhodov, V. A. Rusakov

Southern Federal University, Rostov-on-Don

Abstract: The problem of flows in networks with barrier-type reachability restrictions is considered. We introduce new definitions that allow one to describe a flow in a network with reachability constraints, in particular, a representation of a flow as a vector-valued function. Conditions for preserving the flow and restricting the maximum flow along an arc are formulated in terms of vector-valued functions. This allows one to consider flow problems without passing to an unfolding, which is a graph with connected arcs.

Keywords: graph theory, nonstandard reachability, barrier reachability, network, flow in network, breakthrough algorithm.

UDC: 519.1

MSC: 05C38

DOI: 10.36535/0233-6723-2022-208-24-28



© Steklov Math. Inst. of RAS, 2024