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

Харихаран и коллеги [9] использовали алгоритм из [3] для разработки алгоритма с ожидаемым временем исполнения <math>\tilde{O}(m + nk^3) \; </math> для вычисления частичного дерева Гомори-Ху для представления значений <math>\lambda (s, t) \;</math> для всех пар вершин s и t, удовлетворяющих условию <math>\lambda (s, t) \le k \;</math>. Замена алгоритма из [3] новым алгоритмом вычисления связности по Штейнеру позволяет получить частичное дерево Гомори-Ху за ожидаемое время <math>\tilde{O}(m + nk^2) \; </math>. Балгат и коллеги показали, что при помощи более детального анализа этот результат можно улучшить, предложив следующую теорему.