TY - JOUR
AU - Maehara, Takanori
AU - Inoue, Yuma
PY - 2019/07/17
Y2 - 2022/12/02
TI - Group Decision Diagram (GDD): A Compact Representation for Permutations
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 33
IS - 01
SE - AAAI Technical Track: Knowledge Representation and Reasoning
DO - 10.1609/aaai.v33i01.33012986
UR - https://ojs.aaai.org/index.php/AAAI/article/view/4155
SP - 2986-2994
AB - <p>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 <em>group decision diagram (GDD)</em>, 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.</p>
ER -