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