JournalVolume 6, №2, Special Issue on Information Technologies and ApplicationsFinding strongly connected components in parallel (pages 236-245)
Pogorilyy S.D., Lozytskyi S.I. Abstract. This paper presents the method of a parallel implementation of Tarjan's algorithm that solves an important problem of detection of strongly connected components in a directed graph. A theoretical synthesis of the corresponding scheme of the algorithm is done with the means of systems of modified algorithmic algebras developed by V.M. Glushkov (SAA-M). Theoretical estimations of the speedup of the algorithm are obtained. These estimations have been checked up and confirmed in the experiment.
|
|