| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 431380 | Journal of Discrete Algorithms | 2006 | 21 Pages |
Abstract
We present a symbolic OBDD algorithm for topological sorting which requires O(log2|V|)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|)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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Philipp Woelfel,