Implicit enumeration of strongly connected components
Aiguo Xie, Peter A. Beerel · 1999
This paper presents a BDD-based implicit algorithm to compute all maximal strongly connected components of directed graphs. The algorithm iteratively applies reachability analysis and sequentially identifies SCCs. Experiments suggest that the algorithm dramatically outperforms the only existing implicit method which must compute the transitive closure of the adjacency-matrix of the graphs. 1 Introduction Decomposing a directed graph (digraphs) into its (maximal) strongly connected components (SCCs) is a fundamental graph problem [1] and has many important applications in CAD. Generally speaking, SCC decomposition often divides a digraph problem into subproblems, one for each SCC. The solution to the original problem can be constructed by combining the solutions to the subproblems, sometimes with the aid of the component graph (i.e., the structure of connections among SCCs). Using an explicit data structure such as an adjacencylist or an adjacency-matrix [1], the decomposition of a di...