Research map / Learning theory and algorithms / Combinatorial and search optimization
Dancing with Decision Diagrams: A Combined Approach to Exact Cover
Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add memo cache to DXZ (ablation) | DXZ · domino 10x10 | computation time (s): > 600 -> 0.003 | Improved |
| add memo cache to DXZ (ablation) | DXZ · tetromino 8x8 | computation time (s): > 600 -> 42.62 | Improved |
| replace DLX with DXZ | exact cover solver · domino 10x10 | computation time (s): > 600 -> 0.003 | Improved |
| replace DLX with DXZ | exact cover solver · doublefact-19 | computation time (s): 194.43 -> 0.022 | Improved |
| replace DLX with DXZ | exact cover solver · exotic fives | computation time (s): 97.30 -> 92.87 | No clear effect |
| use fixed column order in DXZ (ablation) | DXZ · tetromino 8x8 | computation time (s): 42.62 -> 0.88 | Improved |
| use fixed column order in DXZ (ablation) | DXZ · sppnw09 | computation time (s): 19.18 -> 67.76 | Hurt |
| use fixed column order in DXZ (ablation) | DXZ · tetromino 6x6 | computation time (s): 0.023 -> 0.013 | Improved |
| use DXZ instead of sharpSAT | model counting · tetromino 6x6 | computation time (s): 155.74 -> 0.023 | Improved |
| use DXZ instead of c2d | compilation · domino 10x10 | computation time (s): 109.45 -> 0.003 | Improved |
| use DXZ without storing solutions (D) vs DLX storing them | DLX · domino 8x8 | computation time (s): 5.21 -> 1.23 | Improved |
Closest papers by meaning
- Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms (ICML 2025 · similarity 0.82)
- Group Decision Diagram (GDD): A Compact Representation for Permutations (AAAI 2019 · similarity 0.82)
- Rethinking Branching on Exact Combinatorial Optimization Solver: The First Deep Symbolic Discovery Framework (ICLR 2024 · similarity 0.81)
- Nested Depth Search (AAAI 2026 · similarity 0.81)
- A Dynamic Algorithm for Weighted Submodular Cover Problem (ICML 2024 · similarity 0.80)
- Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover (AAAI 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
