4446
правок
Полностью динамические минимальные остовные деревья: различия между версиями
Материал из WEGA
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 10:13, 13 марта 2018
, 13 марта 2018→Открытые вопросы
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами в динамической задаче минимального остовного дерева. Заметим, что это возможно для специального случая планарных графов [6]. | Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами в динамической задаче минимального остовного дерева. Заметим, что это возможно для специального случая планарных графов [6]. | ||
Во-вторых, техники поддержки динамических минимальных остовных деревьев могут быть расширены на задачи 2-реберной и 2-вершинной связности, которые могут быть решены за полилогарифмическое время на одно обновление. Можно ли распространить эту технику более высокие | Во-вторых, техники поддержки динамических минимальных остовных деревьев могут быть расширены на задачи 2-реберной и 2-вершинной связности, которые могут быть решены за полилогарифмическое время на одно обновление. Можно ли распространить эту технику на более высокие размерности связности? Это особенно важно, поскольку наилучшие известные границы обновления для более высоких степеней реберной и вершинной связности являются полиномиальными, и было бы очень полезно разработать полилогарифмические алгоритмы хотя бы для полностью динамических задач 3-реберной и 3-вершинной связности. | ||
== См. также == | == См. также == | ||
