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

• Published in: Доповіді НАН України
• Date: 2013
• Main Authors: Ємець, О.О., Ємець, Є.М., Олексійчук, Ю.Ф.
• Format: Article
• Language: Ukrainian
• Published: Видавничий дім "Академперіодика" НАН України 2013
• Subjects: Інформатика та кібернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/85634
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 33–37. — Бібліогр.: 12 назв. — укр.

Розглядається комб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.