Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями
Перейти к навигации
Перейти к поиску
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> на одну операцию.''' | ||