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

Шеной и Руделл [7] реализовали алгоритмы ресинхронизации Лейзерсона и Сакса для нахождения минимального периода и минимальной площади с некоторыми изменениями ради повышения эффективности. Для задачи ресинхронизации с минимальной длительностью они реализовали второй алгоритм, а для поиска неприменимости на более раннем этапе ввели указатель от одной вершины к другой в случае, если между ними требуется наличие хотя бы одного регистра. Цикл, сформированный указателями, свидетельствует о неприменимости данной длительности. В задаче ресинхронизации с минимальной длительностью они устранили некоторую избыточность ограничений и использовали алгоритм масштабирования стоимости Голдберга-Тарьяна [ ] для вычисления потока с минимальной стоимостью.