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

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