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

'''Геометрическая маршрутизация в графах с динамическими ребрами''' [3] применяется к модели, в которой вершины узлы являются безошибочными и стационарными, а ребра меняют статус между ''активным'' и ''неактивным''. Однако при этом предполагается, что, несмотря на динамические изменения топологии, сеть всегда сохраняет связность. В этой модели алгоритм маршрутизации с обходом графа по временным меткам (Timestamp-Traversal) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи.

Альтернативное решение под названием «обходом с ограничением дистанции» (Tethered-Traversal) основывается на наблюдении, согласно которому (вновь) появляющиеся ребра потенциально сокращают пути обхода; у этого решения временная и пространственная сложность процедуры маршрутизации линейны относительно числа вершин n.