The Theory of Zero-Suppressed BDDs and the Number of Knight's Tours |
| |
Authors: | Olaf Schröer Ingo Wegener |
| |
Affiliation: | (1) FB Informatik, LS II, Univ. Dortmund, 44221 Dortmund, Germany |
| |
Abstract: | Zero-suppressed binary decision diagrams (ZBDDs) have been introduced by Minato [14–17] who presents applications for cube set representations, fault simulation, timing analysis and the n-queens problem. Here the structural properties of ZBDDs are worked out and a generic synthesis algorithm is presented and analyzed. It is proved that ZBDDs can be at most by a factor n + 1 smaller or larger than ordered BDDs (OBDDs) for the same function on n variables. Using ZBDDs the best known upper bound on the number of knight's tours on an 8 × 8 chessboard is improved significantly. |
| |
Keywords: | ordered binary decision diagram zero-suppressed binary decision diagram decomposition rules generic synthesis algorithm trade-offs knight's problem |
本文献已被 SpringerLink 等数据库收录! |