4511
правок
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:48, 28 апреля 2016
, 28 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
В качестве модели вычислений в [9] использовалась RAM-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели машины с указателями. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2]. | В качестве модели вычислений в [9] использовалась [[RAM]]-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели [[машина с указателями|машины с указателями]]. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2]. | ||