Деревья Гомори-Ху: различия между версиями

Вместо подпрограмм нахождения максимального потока они использовали алгоритм связности по Штейнеру. Связность по Штейнеру множества вершин S (называемого множеством Штейнера) в неориентированном графе представляет собой минимальный размер разреза, разделяющего S на две части; такой разрез называется минимальным разрезом Штейнера. Обобщая алгоритм упаковки дерева, предложенный Габовым [4], для целей нахождения реберной связности графа, Коул и Харинаран [3] предложили алгоритм нахождения связности k по Штейнеру для множества вершин в неориентированных или ориентированных невзвешенных Эйлеровых графах за время <math>\tilde{O} (mk^2) \; </math>. (Время исполнения в случае неориентированных графов несколько меньше – <math>\tilde{O}(m + nk^3) \; </math>.) Балгат и коллеги улучшили этот результат, предложив следующую теорему.