Ресинхронизация схемы: различия между версиями

В своем втором алгоритме авторы избавились от построения матриц W и D, однако по-прежнему использовали проверку применимости длительности такта во время бинарного поиска. Однако проверка применимости в этот раз выполняется при помощи инкрементной ресинхронизации и работает следующим образом. Начиная с r = 0 алгоритм вычисляет время прибытия в каждую вершину при помощи вычисления самых длинных путей в ориентированном ациклическом графе. Для каждой вершины v, время прибытия в которую превышает заданную длительность <math>\varphi \;</math>, значение r[v] увеличивается на единицу. Процесс вычисления времени прибытия и увеличения r повторяется |V| — 1 раз. Если после этого какое-либо время прибытия остается большим, чем <math>\varphi \;</math>, то длительность является неприменимой. Проверку применимости можно выполнить за время O(|V| |E|), а полное время выполнения ресинхронизации с минимальной длительностью составляет O(|V| |E| log |V|).