Максимальный поток в параллельных сетях со связанными дугами

Широко известная задача поиска максимального потока в классических сетях имеет множество алгоритмов решения, которые обладают полиномиальной вычислительной сложностью от размеров сети. В общем случае задача нахождения максимального потока для сетей со связанными дугами является NP-полной. Однако среди ранее изученных сетей со связанными дугами существуют такие, для которых вычисление максимального потока осуществимо за полиномиальное от размеров сети время. Данная работа посвящена определению влияния топологии сетей со связанными дугами на возможность нахождения для них максимального потока за полиномиальное время. В работе рассматривается класс параллельных сетей со связанными дугами, для которого предложен быстрый полиномиальный алгоритм поиска максимального потока.