Abstract of Paper

Symbolic Topological Sorting with OBDDs
by Philipp Wolfel

Abstract:

We present a symbolic OBDD algorithm for topological sorting which
requires $O(log^2|V|)$ OBDD operations.
Then we analyze its true runtime for the directed grid graph and show
an upper bound of $O(log^4|V|)$.
This is the first true runtime analysis of any symbolic OBDD
algorithm, and it demonstrates that one can hope that the algorithm
behaves well for sufficiently structured inputs.