4446
правок
Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями
Материал из WEGA
Поиск кратчайших путей в планарных графах с отрицательными весами ребер (посмотреть исходный код)
Версия от 14:24, 12 мая 2016
, 12 мая 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
Теорема 4. Для планарных графов, имеющих только ребра с неотрицательными весами, существует динамическая структура данных, поддерживающая ответы на запросы о расстояниях и операции обновления, меняющие веса ребер, за амортизированное время <math>O(n^{2/3} \; log^{7/3} \; n)</math> на одну операцию. Для планарных графов, имеющих ребра с отрицательными весами, существует динамическая структура данных, поддерживающая тот же набор операций с амортизированным временем <math>O(n^{4/5} \; log^{13/5} \; n)</math> на одну операцию. | '''Теорема 4. Для планарных графов, имеющих только ребра с неотрицательными весами, существует динамическая структура данных, поддерживающая ответы на запросы о расстояниях и операции обновления, меняющие веса ребер, за амортизированное время <math>O(n^{2/3} \; log^{7/3} \; n)</math> на одну операцию. Для планарных графов, имеющих ребра с отрицательными весами, существует динамическая структура данных, поддерживающая тот же набор операций с амортизированным временем <math>O(n^{4/5} \; log^{13/5} \; n)</math> на одну операцию.''' | ||
