Group Decision Diagram (GDD): A Compact Representation for Permutations

Authors

  • Takanori Maehara RIKEN
  • Yuma Inoue Google

DOI:

https://doi.org/10.1609/aaai.v33i01.33012986

Abstract

Permutation is a fundamental combinatorial object appeared in various areas in mathematics, computer science, and artificial intelligence. In some applications, a subset of a permutation group must be maintained efficiently. In this study, we develop a new data structure, called group decision diagram (GDD), to maintain a set of permutations. This data structure combines the zero-suppressed binary decision diagram with the computable subgroup chain of the permutation group. The data structure enables efficient operations, such as membership testing, set operations (e.g., union, intersection, and difference), and Cartesian product. Our experiments demonstrate that the data structure is efficient (i.e., 20–300 times faster) than the existing methods when the permutation group is considerably smaller than the symmetric group, or only subsets constructed by a few operations over generators are maintained.

Downloads

Published

2019-07-17

How to Cite

Maehara, T., & Inoue, Y. (2019). Group Decision Diagram (GDD): A Compact Representation for Permutations. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2986-2994. https://doi.org/10.1609/aaai.v33i01.33012986

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning