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(n2) time with O(nL) processors and algorithm (2) runs in O(n3) time with O(nL-1) processors, where the problems dimension is O(nL). Algorithm (3) and (4) runs also in polynomial time. Algorithm (3) runs in O(q) time with O(nL) processors.
Mathematical modelling in actual problems of science and technics