Symbolic Topological Sorting with OBDDs

Abstract. We present a symbolic OBDD algorithm for topological sorting which requires O(log² N) OBDD operations. Then we analyze its true runtime for the directed grid graph and show an upper bound of O(log⁴ N loglog N). 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.

Notes

• Appeared in Journal of Discrete Algorithms, vol. 4, issue 1, pp. 51-71. Elsevier 2006.


• To view the online article click here.


• Extended abstract appeared in
  Mathematical Foundations of Computer Science 2003; 28th International Symposium,
  Lecture Notes in Computer Science 2747, Springer, pp. 671-680, 2002

  BibTeX entry
  

• Extended abstract: pdf, postscript (© Springer)


• Preliminary journal version: pdf, postscript