Computing strongly connected components in a linear number of symbolic steps
Raffaella Gentilini, Carla Piazza, Alberto Policriti · 2003
We present an algorithm that computes in a linear number of symbolic steps (O(jV j)) the strongly connected components (sccs) of a graph G = hV; Ei represented by an Ordered Binary Decision Diagram (OBDD). 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 (jV j log jV j) symbolic steps ([BGS00]).