Компромиссы при решении динамических графовых задач: различия между версиями

Динамическим алгоритмам на графе посвящено множество работ. В числе графовых задач, для которых разработаны эффективные динамические алгоритмы, можно упомянуть задачи о связности графа, о минимальном разрезе, минимальном остовном дереве, транзитивном замыкании и нахождении кратчайших путей (см., например, [ ] и ссылки в этой работе). Многие из них выполняют явное обновление свойства P после каждого обновления графа, чтобы отвечать на запросы за оптимальное время. Этот вариант подходит для случаев, когда обновлений мало, а запросов – много. В приложениях со сравнимым числом обновлений и запросов более эффективным подходом будет попытка уменьшить время обновления – возможно, ценой увеличения времени выполнения запроса. Это обычно достигается при помощи ослабления предположения о том, что свойство P следует поддерживать явным образом.