|Abstract of Paper|
Symbolic Topological Sorting with OBDDs
by Philipp Wolfel
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.