Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams

Nishino, Masaaki; Yasuda, Norihito; Nakamura, Kengo

doi:10.24963/ijcai.2021/275

Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams

Masaaki Nishino, Norihito Yasuda, Kengo Nakamura

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1996-2004.

https://doi.org/10.24963/ijcai.2021/275

Keywords

Knowledge Representation and Reasoning: Knowledge Representation Languages
Heuristic Search and Game Playing: Combinatorial Search and Optimisation

Abstract

Exact cover refers to the problem of finding subfamily

F of a given family of sets S whose universe

is D, where F forms a partition of D. Knuth’s Algorithm

DLX is a state-of-the-art method for solving

exact cover problems. Since DLX’s running

time depends on the cardinality of input S, it can be

slow if S is large. Our proposal can improve DLX

by exploiting a novel data structure, DanceDD,

which extends the zero-suppressed binary decision

diagram (ZDD) by adding links to enable efficient

modifications of the data structure. With DanceDD,

we can represent S in a compressed way and perform

search in linear time with the size of the structure

by using link operations. The experimental results

show that our method is an order of magnitude

faster when the problem is highly compressed.

Masaaki Nishino, Norihito Yasuda, and Kengo Nakamura. 2021. Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1996–2004. https://doi.org/10.24963/ijcai.2021/275

@inproceedings{ijcai2021p275,
  title     = {Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams},
  author    = {Nishino, Masaaki and Yasuda, Norihito and Nakamura, Kengo},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {1996--2004},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/275},
  url       = {https://doi.org/10.24963/ijcai.2021/275},
}

TY  - CPAPER
TI  - Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams
AU  - Nishino, Masaaki
AU  - Yasuda, Norihito
AU  - Nakamura, Kengo
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 1996
EP  - 2004
DO  - 10.24963/ijcai.2021/275
UR  - https://doi.org/10.24963/ijcai.2021/275
ER  -