Parallel algorithms for prefractal graphs

This paper is devoted to parallel algorithms for solving the following prefractal graph problems: finding (1) a minimum spanning tree, (2) a perfect matching, (3) an Eulerian cycle, (4) a Hamiltonian cycle. Algorithm (1) runs in $O(n^2)$ time with $O(n^L)$ processors and algorithm (2) runs in $O(n^3)$ time with $O(n^{L-1})$ processors, where the problems dimension is $O(n^L)$. Algorithm (3) and (4) runs also in polynomial time. Algorithm (3) runs in $O(q)$ time with $O(n^L)$ processors.