A Parallel Approach to Counting Exact Covers Based on Decomposability Property
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911597509738496 |
|---|---|
| author | Fang, Liangda Luo, Yaohui Li, Delong Huang, Xuanxiang Guan, Quanlong |
| author_facet | Fang, Liangda Luo, Yaohui Li, Delong Huang, Xuanxiang Guan, Quanlong |
| contents | The exact cover problem is a classical NP-hard problem with broad applications in the area of AI. Algorithm DXZ is a method to count exact covers representing by zero-suppressed binary decision diagrams (ZBDDs). In this paper, we propose a zero-suppressed variant of decision decomposable negation normal form (in short, decision-ZDNNF), which is strictly more succinct than ZBDDs. We then design a novel parallel algorithm, namely DXD, which constructs a decision-ZDNNF representing the set of all exact covers. Furthermore, we improve DXD by dynamically updating connected components. The experimental results demonstrate that the improved DXD algorithm outperforms all of state-of-the-art methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14627 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Parallel Approach to Counting Exact Covers Based on Decomposability Property Fang, Liangda Luo, Yaohui Li, Delong Huang, Xuanxiang Guan, Quanlong Artificial Intelligence The exact cover problem is a classical NP-hard problem with broad applications in the area of AI. Algorithm DXZ is a method to count exact covers representing by zero-suppressed binary decision diagrams (ZBDDs). In this paper, we propose a zero-suppressed variant of decision decomposable negation normal form (in short, decision-ZDNNF), which is strictly more succinct than ZBDDs. We then design a novel parallel algorithm, namely DXD, which constructs a decision-ZDNNF representing the set of all exact covers. Furthermore, we improve DXD by dynamically updating connected components. The experimental results demonstrate that the improved DXD algorithm outperforms all of state-of-the-art methods. |
| title | A Parallel Approach to Counting Exact Covers Based on Decomposability Property |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2604.14627 |