Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі

Abstract

Розглядається комбiнаторна задача знаходження максимального потоку в мережi, яка зводиться до евклiдової комбiнаторної задачi на розмiщеннях. Запропоновано наближений алгоритм для її розв’язання, визначено полiномiальну оцiнку його складностi.

Рассматривается комбинаторная задача нахождения максимального потока в сети, которая сводится к эвклидовой комбинаторной задаче на размещениях. Предложен приближенный алгоритм для ее решения, определена полиномиальная оценка его сложности.

The combinatorial problem finding of the maximal flow in a network is considered. This problem is a Euclidean combinatorial one on arrangements. An approximate algorithm for the solution of this problem is proposed. The polynomial estimation of the complexity of this algorithm is found.