Распределенный поиск компонент сильной связности в адаптивной модели

В работе исследуется сложностная оценка алгоритма поиска компонент сильной связности в Adaptive Massively Parallel Computations(AMPC) модели. Данная модель, в отличие от иных более ограниченных распределенных формализаций, позволяет в рамках одного шага алгоритма строить дерево запросов в распределенную память. Получен вероятностный алгоритм, реализующий поиск компонент сильной связности за полилогарифмическое или сублинейное время, в зависимости от объема доступной локальной памяти. Объем требуемой локальной памяти является сублинейной величиной по отношению к числу вершин в графе.