Authorization

 

Journal

Volume 6, №2, Special Issue on Information Technologies and Applications


Finding 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.


Keywords: Tarjan's Algorithm, Strongly Connected Component, Depth-First Search, Formal Theories of Algorithms, Paralleling of an Algorithm.

 



COIA 2027

7-9 July 2027
Baku, Azerbaijan

Search