4431
правка
Деревья Гомори-Ху: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
Все предыдущие алгоритмы построения деревьев Гомори-Ху в неориентированных графах использовали подпрограммы нахождения максимального потока. Гомори и Ху показали, как вычислить динамическое дерево T при помощи n – 1 операций вычисления максимального потока и операций сжатия графа. Гусфилд [8] предложил алгоритм, не использующий операций | Все предыдущие алгоритмы построения деревьев Гомори-Ху в неориентированных графах использовали подпрограммы нахождения максимального потока. Гомори и Ху показали, как вычислить динамическое дерево T при помощи n – 1 операций вычисления максимального потока и операций сжатия графа. Гусфилд [8] предложил алгоритм, не использующий операций сжатия графа; все n – 1 операций вычисления максимального потока выполняются на исходном графе. Голдберг и Цюцюликлис [6] выполнили экспериментальное исследование алгоритмов, предложенных Гомори и Ху, а также Гусфилдом, для решения задачи поддержания динамического дерева, и описали эффективные реализации этих алгоритмов. Бенцур [1] привел примеры, демонстрирующие, что динамические деревья с отрезанием не существуют для ориентированных графов. | ||
Любой подход к построению дерева Гомори-Ху, основанный на нахождении максимального потока, будет исполняться за время, в (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>. | Любой подход к построению дерева Гомори-Ху, основанный на нахождении максимального потока, будет исполняться за время, в (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>. | ||