NP-трудность комбинаторной задачи нахождения максимального потока

Журнал: 
Страница: 
36
УДК: 
519.85
В статье рассмотрена задача нахождения максимального потока с дополнительными комбинаторными ограничениями, которая является обобщением классической задачи нахождения максимального потока. Доказана NP-трудность задачи. 
info_eng: 
In article is proposed the maximum flow problem with additional combinatorial restrictions. This problem is generalization of the classical maximum flow problem. In article NP-hard of a problem is proved.