Применение геометрических остовных сетей: различия между версиями

'''Теорема 9. Пусть даны – геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить <math>(1 + \varepsilon) \; </math>-аппроксимацию t.'''

*' [[Алгоритм поиска кратчайших путей в разреженных графах]]

*' [[Алгоритм поиска кратчайших путей при помощи матричного произведения]]

*' [[Геометрические остовы]]

*' [[Планарные геометрические остовы]]

*' [[Разреженные остовы графов]]

*' [[Синхронизаторы, остовы]]