TCS-TR-A-13-69

Date: Tue Dec 17 16:02:22 2013

Title: Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

Authors: Hiroaki Iwashita and Shin-ichi Minato

Contact:

First name: Shin-ichi
Last name: Minato
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan.
Email: minato@ist.hokudai.ac.jp

Abstract. Many important problems of graph enumeration and indexing can be solved by frontier-based methods, which construct ZDDs in a breadth-first manner from the top to the bottom. We present new techniques toward an efficient framework to deal with the frontier-based methods. Ad hoc parts of the algorithm are encapsulated using the recursive specifications that represent properties to be compiled into a ZDD. In this framework, we can apply the ZDD node deletion rule on the fly, while conventional methods does not take it into account. Operations on the recursive specifications, which allow us to combine multiple properties without constructing ZDD structure for each property, are also introduced. These techniques are applicable to existing frontier-based methods and accelerates even Knuth’s sophisticated path enumeration algorithm doubly.