ZDDs and Enumeration Problems: State-of-The-Art Techniques and Programming Tool

DOI IR IR (HANDLE)
  • TODA Takahisa
    Graduate School of Informatics and Engineering, the University of Electro-Communications
  • SAITOH Toshiki
    Graduate School of Engineering, Kobe University
  • IWASHITA Hiroaki
    Knowledge Information Processing Laboratory, Fujitsu Laboratories Ltd
  • KAWAHARA Jun
    Graduate School of Information Science, Nara Institute of Science and Technology
  • MINATO Shin-ichi
    Graduate School of Information Science and Technology, Hokkaido University

Bibliographic Information

Other Title
  • ZDDと列挙問題―最新の技法とプログラミングツール
Published
2017
Resource Type
journal article
DOI
  • 10.11309/jssst.34.3_97
Publisher
Japan Society for Software Science and Technology

Search this article

Description

Combinatorial enumeration problems are to find all combinations of items (solutions) that satisfy given constraints. There are many applications to various problems that are closely related to real-life such as power distribution network analysis. Recent researches have paid attention to a generic framework for computing various combinatorial enumeration problems through the method of efficiently constructing the data structure, ZDD, for all solutions of those problems in a top-down fashion, which is thus called top-down ZDD construction. The paper focuses on this subject and provides a comprehensive survey on algorithms that the construction is based on, an extended method for efficiently handling complicated constraints, the basics of the programming tool, TdZdd, that allows us to easily develop top-down construction-based programs, and practical programming examples of some applied problems.

Journal

  • Computer Software

    Computer Software 34 (3), 3_97-3_120, 2017

    Japan Society for Software Science and Technology

Details 詳細情報について

Report a problem

Back to top