Symbolic topological sorting with OBDDs

AbstractWe present a symbolic OBDD algorithm for topological sorting which requires O(log2|V|) OBDD operations. Then we analyze its true runtime for the directed grid graph and show an upper bound of O(log4|V|⋅loglog|V|). This is the first true runtime analysis of a symbolic OBDD algorithm for a fundamental graph problem, and it demonstrates that one can hope that the algorithm behaves well for sufficiently structured inputs