Параллельные алгоритмы на предфрактальных графах

Работа посвящена параллельным алгоритмам решения некоторых задач на предфрактальных графах: поиск (1) остовного дерева минимального веса, (2) совершенного паросочетания, (3) эйлеровой цепи, (4) гамильтонова цикла. Алгоритм (1) исполняется за время $O(n^2)$, используя $O(n^L)$ процессоров, а алгоритм (2) за время $O(n^3)$ при использовании $O(n^{L-1})$ процессоров, где размерность обоих задач $O(n^L)$. Алгоритмы (3) и (4) также исполняются за полиномиальное время. Алгоритм (3) исполняется за время $O(q)$, используя $O(n^L)$ процессоров.