Implicit enumeration of strongly connected components

Author

Aiguo Xie ; Beerel, P.A.

Author_Institution

Dept. of Electr. Eng. Syst., Univ. of Southern California, Los Angeles, CA, USA

fYear

1999

fDate

7-11 Nov. 1999

Firstpage

37

Lastpage

40

Abstract

This paper presents a binary decision diagram (BDD) based implicit algorithm to compute all maximal strongly connected components (SCCs) 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.

Keywords

binary decision diagrams; data structures; directed graphs; iterative methods; matrix algebra; reachability analysis; software performance evaluation; algorithm performance; binary decision diagram; directed graphs; graph adjacency matrix transitive closure computation; implicit enumeration; maximal strongly connected components; reachability analysis; sequential component identification; Algorithm design and analysis; Automata; Binary decision diagrams; Boolean functions; Data structures; Engineering profession; Iterative algorithms; Partitioning algorithms; Reachability analysis; State-space methods;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer-Aided Design, 1999. Digest of Technical Papers. 1999 IEEE/ACM International Conference on

Conference_Location

San Jose, CA, USA

ISSN

1092-3152

Print_ISBN

0-7803-5832-5

Type

conf

DOI

10.1109/ICCAD.1999.810617

Filename

810617