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

'''Теорема 10 [5]. После предварительной обработки запросы с единственным источником требуют O(c) времени, а с несколькими источниками – O(c log n) времени в графах единичных дисков, обладающих свойством графов Гэбриэла.'''

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