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

Любой подход к построению дерева Гомори-Ху, основанный на нахождении максимального потока, будет исполняться за время, в (n – 1) раз большее времени единичного вычисления максимального потока. До сих пор все более быстрые алгоритмы построения деревьев Гомори-Ху были побочными продуктами более быстрых алгоритмов нахождения максимального потока. Самый быстрый на данный момент алгоритм нахождения максимального потока с временем <math>\tilde{O} (m + n \lambda (s, t))</math> (полилогарифмические сомножители n в <math>\tilde{O}</math>-нотации игнорируются), авторами которого были Каргер и Левайн [10], дает наилучшее ожидаемое время исполнения для алгоритма построения дерева Гомори-Ху на простых невзвешенных графах с n вершинами, равное <math>\tilde{O} (n^3) \; </math>. Балгат и коллеги [2] улучшили эту временную сложность до <math>\tilde{O} (mn) \; </math>. Заметим, что оба вышеупомянутых алгоритма являются рандомизированными алгоритмами Лас-Вегаса. Самый быстрый детерминированный алгоритм для задачи построения дерева Гомори-Ху является побочным продуктом алгоритма нахождения максимального потока Голдберга-Рао [5] и имеет время исполнения <math>\tilde{O} (nm^{1/2} min(m, n^{3/2}))</math>.

Харихаран и коллеги [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>. Балгат и коллеги показали, что при помощи более детального анализа этот результат можно улучшить, предложив следующую теорему.

Задача дерандомизации алгоритма, предложенного Балгатом и коллегами [2], с целью создания детерминированного алгоритма построения дерева Гомори-Ху на невзвешенных неориентированных графах с временем исполнения <math>\tilde{O} (mn) \; </math> остается открытой. Еще одна нерешенная задача – расширение результатов работы [2] на взвешенные графы.

Голдберг и Цюцюликлис [6] выполнили широкомасштабное экспериментальное исследование алгоритмов, предложенных Гомори и Ху, а также Гусфилдом, для решения задачи поддержания динамического дерева. Они продемонстрировали варианты эффективной реализации этих алгоритмов, а также предложили и оценили эвристики для ускорения их исполнения. Согласно их наблюдениям, алгоритм Гусфилда во многих ситуациях работает быстрее, зато алгоритм Гомори и Ху более надежен. Более детальное описание результатов экспериментов можно найти в [6].