1294
правки
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 03:41, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) мНет описания правки |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 62: | Строка 62: | ||
Границы, приведенные в теоремах 1 и 2, не могут сравниваться непосредственно, поскольку каждая из них жертвует оптимальностью времени | Границы, приведенные в теоремах 1 и 2, не могут сравниваться непосредственно, поскольку каждая из них жертвует оптимальностью времени выполнения одной операции (либо запроса, либо обновления) ради улучшения времени выполнения другой. | ||
| Строка 94: | Строка 94: | ||
* ''[[Полностью динамические минимальные остовные деревья]] | * ''[[Полностью динамические минимальные остовные деревья]] | ||
* ''[[Полностью динамическая проверка на планарность]] | * ''[[Полностью динамическая проверка на планарность]] | ||
* ''[[Полностью | * ''[[Полностью динамический алгоритм транзитивного замыкания]] | ||
== Литература == | == Литература == | ||
| Строка 135: | Строка 135: | ||
18. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350 | 18. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350 | ||
[[Категория: Совместное определение связанных терминов]] | |||
