×

zbMATH — the first resource for mathematics

Computing strongly connected components in a linear number of symbolic steps. (English) Zbl 1092.68716
Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 573-582 (2003).
Summary: We present an algorithm that computes in a linear number of symbolic steps \((O(|V|))\) the strongly connected components (sccs) of a graph \(G=\langle V,E\rangle\) represented by an ordered binary decision diagram. This result matches the complexity of the (celebrated) Tarjan’s algorithm operating on explicit data structures. To date, the best algorithm for the above problem works in \(\Theta(|V|\log|V|)\) symbolic steps.
For the entire collection see [Zbl 1006.00017].

MSC:
68W05 Nonnumerical algorithms
68R10 Graph theory (including graph drawing) in computer science
Software:
CUDD
PDF BibTeX XML Cite