Skip to Main content Skip to Navigation
Conference papers

SLIDE: A Useful Special Case of the CARDPATH Constraint

Abstract : We study the CARDPATH constraint. This ensures a given constraint holds a number of times down a sequence of variables. We show that SLIDE, a special case of CARDPATH where the slid constraint must hold always, can be used to encode a wide range of sliding sequence constraints including CARDPATH itself. We con- sider how to propagate SLIDE and provide a complete propagator for CARDPATH. Since propagation is NP-hard in general, we identify special cases where propagation takes polynomial time. Our experi- ments demonstrate that using SLIDE to encode global constraints can be as efficient and effective as specialised propagators.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Christian Bessiere Connect in order to contact the contributor
Submitted on : Monday, October 13, 2008 - 3:27:48 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM


  • HAL Id : lirmm-00329876, version 1



Christian Bessière, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh. SLIDE: A Useful Special Case of the CARDPATH Constraint. ECAI: European Conference on Artificial Intelligence, Jul 2008, Patras, Greece. pp.475-479. ⟨lirmm-00329876⟩



Record views


Files downloads