TCS-TR-A-13-62

Date: Thu Apr 11 20:31:46 2013

Title: Fast Construction of ZDDs from Large-scale Hypergraphs

Authors: Takahisa Toda

Contact:

First name: Takahisa
Last name: Toda
Address: Eng. C306, Graduate School of Information Science and Technololgy, Hokkaido University, North 14 West 9, Sapporo, 060-0814 Japan
Email: toda@erato.ist.hokudai.ac.jp

Abstract. We present an algorithm to compress hypergraphs into the data structure ZDDs and analyze the computational complexity. Since a ZDD provides an approach to solve large-scale problems that are difficult to compute in a reasonable amount of time and space, it is important to compress hypergraphs efficiently. Our algorithm uses multikey Quicksort given by Bentley and Sedgewick. By conducting experiments with various datasets, we show that our algorithm is significantly faster and requires smaller memory than an existing method.