Alternative Algorithm for finding the strongly connected components of a graph

Authors

  • Adrian Deaconu Transilvania University of Brasov, Romania

Keywords:

strongly connected components, condensed graph, depth search, time complexity

Abstract

An alternative O(n2) algorithm for finding the strongly connected components of a graph is presented. This algorithm is much easier to apply in practice than the classic algorithm that uses two graph depth searches.

Author Biography

Adrian Deaconu, Transilvania University of Brasov, Romania

Faculty of Mathematics and Informatic

Published

2007-05-24

Issue

Vol. 13(48) (2006)

Section

MATHEMATICS, INFORMATICS