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

• Veröffentlicht in: Доповіді НАН України
• Datum: 2013
• Hauptverfasser: Ємець, О.О., Ємець, Є.М., Олексійчук, Ю.Ф.
• Format: Artikel
• Sprache: Ukrainian
• Veröffentlicht: Видавничий дім "Академперіодика" НАН України 2013
• Schlagworte: Інформатика та кібернетика
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/85634
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Допов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.