Географическая маршрутизация: различия между версиями

'''Теорема 1. Если между источником и адресатом есть связь, алгоритм Face Routing, выполняемый на произвольном планарном графе, всегда находит путь к вершине-адресату. Его выполнение требует не более O(n) шагов, где n – общее количество вершин в сети.'''

'''Теорема 2. Пусть c – стоимость оптимального пути из s в t в заданном графе единичных дисков. Стоимость достижения алгоритмом GOAFR+ вершины t составляет <math>O(c^2) \;</math>, если между s и t имеется связь. Если s и t не связаны между собой, GOAFR+ сообщает об этом источнику.'''

'''Теорема 3. Существуют графы, на которых любой детерминированный (рандомизированный) децентрализованный алгоритм маршрутизации имеет (ожидаемую) стоимость <math>\Omega(c^2) \;</math>.'''

'''Теорема 4. Затраты на достижение алгоритмом GOAFR+ вершины-адресата в графе единичных дисков являются асимптотически оптимальными.'''