KIAM Main page Web Library  •  Publication Searh  Русский 

KIAM Preprint № 84, Moscow, 2003
Authors: Kochkarov A.A., Kochkarov R.A.
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(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.
Publication language: russian, pages: 18
Research direction:
Mathematical modelling in actual problems of science and technics
Source text: