Геометрические остовы: различия между версиями

[[Жадный алгоритм]] был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если кратчайший путь в G между u и v не превышает t • |uv|, то ребро (u, v) отбрасывается, в противном случае оно добавляется к частичному остовному графу G.

Используя свойство прыжков, можно ограничить вес графа. Дас и Нарасимхан [10] заметили, что жадный остов можно вычислить приближенно при удовлетворении свойства прыжков. Это наблюдение позволило разработать более быстрые алгоритмы для его построения.