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

Любой подход к построению дерева Гомори-Ху, основанный на нахождении максимального потока, будет исполняться за время, в (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>.

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

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

Теорема 3. Частичное дерево Гомори-Ху для невзвешенного неориентированного графа для представления всех значений <math>\lambda (s, t) \;</math>, не превышающих k, может быть построено за ожидаемое время <math>\tilde{O} (mk)</math>.

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

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