Skip to Main content Skip to Navigation
Journal articles

From MDD to BDD and Arc consistency

Abstract : In this paper, we present a new conversion of multivalued decision diagrams (MDD) to binary decision diagrams (BDD) which can be used to improve MDD-based fil- tering algorithms such as MDDC or MDD-4R. We also propose BDDF, an algorithm that copies modified parts of the BDD “on the fly” during the search of a solution, and yields a better incrementality than a pure MDDC-like approach. MDDC is not very efficient when used to represent poorly structured positive table constraints. Our new representation combined with BDDF retains the properties of the MDD representation and has comparable performances to the STR2 algorithm by Ullmann (2007) and Lecoutre (Constraints, 16.4, 341–371 2011).
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03400583
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 9:48:37 AM
Last modification on : Wednesday, November 3, 2021 - 5:22:08 AM

Identifiers

Collections

Citation

Julien Vion, Sylvain Piechowiak. From MDD to BDD and Arc consistency. Constraints, Springer Verlag, 2018, 23 (4), pp.451-480. ⟨10.1007/s10601-018-9286-5⟩. ⟨hal-03400583⟩

Share

Metrics

Record views

3